python递归尾部函数 python尾递归优化

Python的尾递归

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

创新互联专业为企业提供营口网站建设、营口做网站、营口网站设计、营口网站制作等企业网站建设、网页设计与制作、营口企业网站模板建站服务，10多年营口做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

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递归函数怎样理解

递归的思想主要是能够重复某些动作，比如简单的阶乘，次方，回溯中的八皇后，数独，还有汉诺塔，分形。

由于堆栈的机制，一般的递归可以保留某些变量在历史状态中，比如你提到的return

x

*

power...,

但是某些或许庞大的问题或者是深度过大的问题就需要尽量避免递归，因为可能会栈溢出。还有一个问题是～python不支持尾递归优化！！！！所以～还是尽量避免递归的出现。

def

power(x,

n)

if

n

0:

return

1

return

x

*

power(x,

n

-

1)

power(3,

3)

3

*

power(3,

2)

3

*

(3

*

power(3,

1))

3

*

(3

*

(3

*

power(3,

0)))

3

*

(3

*

(3

*

1))

这里n

=

0,

return

1

3

*

(3

*

3)

3

*

9

27

当函数形参n=0的时候，开始回退～直到第一次调用power结束。

Python进阶 —— 尾递归

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

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

常规递归阶乘：

我们来看一下执行过程：

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

我们再看下执行过程：

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

常规递斐波那契数列：

而尾递归：

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

如何理解python中的递归函数

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

计算机科学家尼克劳斯·维尔特如此描述递归：

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。

python 2 递归函数和其它语言，基本没有差别，只是不支持尾递归。无限递归最大值为固定的，但可以修改。

作者：黄哥