L32 Tail Calls
- python不是很纯粹满足尾递归的语言
- Scheme严格满足尾递归
-
函数式编程有三个特征 --- 需要满足尾递归
- 所有函数都是纯函数
- 不允许重新赋值和不允许可变数据类型
- 名称-值绑定是永久的 --- 没有 for while 循环控制流
-
尾递归
- 尾递归通过淘汰递归调用时不需要的Frame(Frame复用，见example中的reFrame)实现常数级空间利用，尾递归是通过尾调用实现的
- 线性递归一般都可以改写成尾递归，但是并非所有线性递归都是尾递归
-
Tail Calls 尾调用
- 如果除了返回表达式的值之外没有其他事要做就是一个尾调用
- 具体讲，尾调用是在尾上下文中的函数调用，尾上下文指如下情况
lambda或define表达式的最后一个子表达式- 如果整个
if表达式处于尾上下文中，则结果项和替代项也处于其中 - 如果整个
cond表达式处于尾上下文中，则所有非predicate的子表达式也处于其中 - 如果
and和or在尾上下文中，and和or的最后一个子表达式 - 如果
begin在尾上下文中，begin的最后一个子表达式 - 除此之外均非尾调用
-
尾调用与尾递归分析
- 满足上述情况(在尾上下文中)的调用就是尾调用，而递归函数中的所有==递归调用==(不是所有调用)都是尾调用就是尾递归函数
-
尾递归分析过程
- 先找所有的递归调用
- 再看每个递归调用是否都是尾调用
-
Map 和 Reduce