Python小白从挖坑到脱坑之路032_什么是尾递归

大头目

作者：匿名用户
链接：https://www.zhihu.com/question/20761771/answer/19996299
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。SICP中描述了一个内存占用曲线，用以上答案中的Python代码为例（普通递归）：

1. def recsum(x):
   
2.   if x == 1:
   
3.     return x
   
4.   else:
   
5.     return x + recsum(x - 1)

复制代码

当调用recsum(5)，Python调试器中发生如下状况：

1. recsum(5)
   
2. 5 + recsum(4)
   
3. 5 + (4 + recsum(3))
   
4. 5 + (4 + (3 + recsum(2)))
   
5. 5 + (4 + (3 + (2 + recsum(1))))
   
6. 5 + (4 + (3 + (2 + 1)))
   
7. 5 + (4 + (3 + 3))
   
8. 5 + (4 + 6)
   
9. 5 + 10
   
10. 15

复制代码

这个曲线就代表内存占用大小的峰值，从左到右，达到顶峰，再从右到左收缩。而我们通常不希望这样的事情发生，所以使用迭代，只占据常量stack space(更新这个栈！而非扩展他)。---------------------（一个替代方案：迭代）

1. for i in range(6):
   
2.   sum += i

复制代码

因为Python，Java，Pascal等等无法在语言中实现尾递归优化(Tail Call Optimization, TCO)，所以采用了for, while, goto等特殊结构代替recursive的表述。Scheme则不需要这样曲折地表达，一旦写成尾递归形式，就可以进行尾递归优化。---------------------Python中可以写（尾递归）：

1. def tailrecsum(x, running_total=0):
   
2.   if x == 0:
   
3.     return running_total
   
4.   else:
   
5.     return tailrecsum(x - 1, running_total + x)

复制代码

理论上类似上面：

1. tailrecsum(5, 0)
   
2. tailrecsum(4, 5)
   
3. tailrecsum(3, 9)
   
4. tailrecsum(2, 12)
   
5. tailrecsum(1, 14)
   
6. tailrecsum(0, 15)
   
7. 15

复制代码

观察到，tailrecsum(x, y)中形式变量y的实际变量值是不断更新的，对比普通递归就很清楚，后者每个recsum()调用中y值不变，仅在层级上加深。所以，尾递归是把变化的参数传递给递归函数的变量了。怎么写尾递归？形式上只要最后一个return语句是单纯函数就可以。如：return tailrec(x+1);而return tailrec(x+1) + x;则不可以。因为无法更新tailrec()函数内的实际变量，只是新建一个栈。但Python不能尾递归优化（Java不行，C可以，我不知道为什么），这里是用它做个例子。