Tail Recursion 尾递归

昨天做LeetCode的时候发现一个词，Tail Recursion。今天来简单介绍。

Q：sum(5) = 1 + 2 + 3 + 4 + 5 = 15； 为了简单我们用Python

1、普通递归：

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

python解释器会做如下动作。

"""
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)))
15
"""
           

2、尾递归

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

递归过程：

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

3、小结

【1】在尾递归中，其实只有前进的过程，也就是顺藤摸瓜（瓜就是返回结果）。摸到瓜结束。

【2】在普通递归中，我们摸到了瓜（这个瓜在这里指的是递归的base case），你还得记住你怎了顺的藤（将中间过程压栈），然后在把瓜顺着藤捣腾回去（栈的回退），直到到了最初的起点（栈空）。然后返回。

4、比较

@为什么尾递归他比递归少了那么多步骤，还不用建立栈呢？

其实，他开始的时候有一个变量，我们每次迭代都会Update这个变量。这就省去了入栈出栈的过程。节省了很多空间和时间啊。

@那二者还有其他的差别吗？

有的，其实，这道题是sum（5），那我下次sum（10000000），会怎么样呢？

递归： the stack will overflow

尾递归：不会 stack overflow

相对于尾递归，普通递归不是省油的灯啊

我理解，尾递归的效率（包括时间空间） == 循环