我的递归从不爆栈

聊算法的时候，「递归」是避不开的一种技巧，因为很多算法其实会借助此技巧去实现。

那么问题来了，用不好递归会「爆栈」➡️➡️➡️ StackOverFlow

but ! 「尾递归」不会爆栈！

那么尾递归相比正常递归有什么特点呢？

1. 尾调用函数本身，没有多余计算逻辑。
2. 优化栈空间，从O(n)到O(1)

---

以 Python 为例，主要区分普通递归和尾递归对栈空间的使用：

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

调用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
1
2
3
4
5
6
7
8
9
10

可观察，堆栈从左到右，增加到一个峰值后再计算从右到左缩小，这往往是我们不希望的。修改以上代码，可以成为尾递归：

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

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

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

ps : tailrecsum(4, 5) 执行的时候，tailrecsum(5, 0) 在栈上其实就可以回收掉了。

可以看到尾递归相比普通递归，栈空间做到了O(1)的复杂度，也就起到了内存优化的作用。
那么因为是O(1)复杂度，就肯定不会爆栈了。

---

引用

• 尾调用