python尾递归函数,python求递归函数

python为什么不支持尾递归

Python本身是不支持尾递归的(via)，并且对递归次数有限制的，当递归次数超过1000次的时候，就会抛出“RuntimeError: maximum recursion depth exceeded”异常。

Python的尾递归

原因很多人的都知道，让我们先回顾一下函数调用的大概过程：

1）调用开始前，调用方（或函数本身）会往栈上压相关的数据，参数，返回地址，局部变量等。

2）执行函数。

3）清理栈上相关的数据，返回。

因此，在函数 A 执行的时候，如果在第二步中，它又调用了另一个函数 B，B 又调用 C.... 栈就会不断地增长不断地装入数据，当这个调用链很深的时候，栈很容易就满 了，这就是一般递归函数所容易面临的大问题。

而尾递归在某些语言的实现上，能避免上述所说的问题，注意是某些语言上，尾递归本身并不能消除函数调用栈过长的问题，那什么是尾递归呢？在上面写的一般递归函数 func() 中，我们可以看到，func(n) 是依赖于 func(n-1) 的，func(n) 只有在得到 func(n-1) 的结果之后，才能计算它自己的返回值，因此理论上，在 func(n-1) 返回之前，func(n)，不能结束返回。因此func(n)就必须保留它在栈上的数据，直到func(n-1)先返回，而尾递归的实现则可以在编译器的帮助下，消除这个限制

Python进阶 —— 尾递归

下面是笔者的个人理解： 把计算出的值存在函数内部（当然不止尾递归）是其计算方法，从而不用在栈中去创建一个新的，这样就大大节省了空间。函数调用中最后返回的结果是单纯的递归函数调用（或返回结果）就是尾递归。

实例还是和笔者的上一篇文章相同，建议读者阅读 Python —— 递归

常规递归阶乘：

我们来看一下执行过程：

但是如果把上面的函数写成如下形式：

我们再看下执行过程：

很直观的就可以看出，这次的 factorial 函数在递归调用的时候不会产生一系列逐渐增多的中间变量了，而是将状态保存在 acc 这个变量中。而这种形式的递归，就叫做尾递归。

常规递斐波那契数列：

而尾递归：

一下子就充满了逼格，还高效了许多，何乐而不为呢！