若函数在尾位置调用自身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用,即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用,但是尾递归特别有用,也比较容易实现。
尾递归在普通尾调用的基础上,多出了2个特征:
1.在尾部调用的是函数自身 (Self-called);
2.可通过优化,使得计算仅占用常量栈空间 (Stack Space)。

优化尾递归的分析与示例

def recsum(x):
  if x == 1:
    return x
  else:
    return x + recsum(x - 1)

调用recsum(5)为例,栈空间变化:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

可观察,堆栈从左到右,增加到一个峰值后再计算从右到左缩小,这往往是我们不希望的,所以在C语言等语言中设计for, while, goto等特殊结构语句,使用迭代、尾递归,对普通递归进行优化,减少可能对内存的极端消耗。修改以上代码,可以成为尾递归:

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

对比后者尾递归对内存的消耗:

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

则是线性的。