Python函数递归(带实例演示),递归python例子

　　递归的概念非常简单。如果函数包含对自身的调用，则该函数是递归的。

　　在数学和计算机科学中，递归是指在函数的定义中使用函数本身的方法。

　　使用递归时，应注意以下几点：

　　递归是在过程或函数中调用自己。

　　必须有一个明确的递归结束条件，称为递归退出。

　　注意：不要忘记递归退出，避免无限调用函数。

　　递归基本步骤

　　每个递归程序都遵循相同的基本步骤：

　　1.初始化算法。递归程序通常需要在开始时使用一个种子值。要完成这项任务，您可以向函数传递参数，或者提供一个入口函数，该函数是非递归的，但可以为递归计算设置种子值。

　　2.检查要处理的当前值是否与基线条件匹配(基本情况)。如果匹配，它将被处理并返回一个值。

　　3.用一个更小或更简单的子问题(或多个子问题)来重新定义答案。

　　4.对子问题运行算法。

　　5.将结果组合成答案的表达式。

　　6.返回结果。

　　基线条件(基本情况)。基线条件是递归程序的最低位置。在这个位置，不需要再次操作，可以直接返回一个结果。所有递归程序必须至少有一个基线条件，并且必须保证最终达到某个基线条件；否则，程序将永远运行，直到耗尽内存或堆栈空间。

　　主要应用范围

　　递归算法通常用于解决三种问题：

　　(1)数据的定义是递归定义的。(比如斐波那契函数)

　　(2)用递归算法实现问题求解。(回溯)

　　(3)递归定义数据的结构。(比如树遍历，图搜索)

　　典型算法

　　大多数学过数学、计算机科学或者读过编程相关书籍的人，肯定会遇到阶乘：

　　n！=1 2 3 … n

　　它也可以递归定义：

　　n！=(n-1)！ n

　　其中n=1和0！=1。

　　因为它简单明了，所以经常被用作递归的例子。

　　PS:除了阶乘，还有很多算法可以用递归来处理，比如斐波那契数列，汉诺塔等等。

　　def factorial(n)的非递归实现：

　　结果=1

　　对于范围(2，n ^ 1)中的I:

　　结果*=i

　　回送结果

　　阶乘函数def factorial(n)的递归实现；

　　如果n==0或n==1:返回1

　　否则：返回(n *阶乘(n - 1))

　　递归过程

　　为了明确递归步骤，5！流程分解：factorial(5) #第一次调用使用5

　　5 *阶乘(4) #第二次调用使用4

　　5 * (4 *阶乘(3)) #第三个调用使用3

　　5 * (4 * (3 *阶乘(2))) #第四次调用使用2

　　5 * (4 * (3 * (2 *阶乘(1))) #第5次调用使用1

　　5 * (4 * (3 * (2 * 1))) #从第5次调用返回

　　5 * (4 * (3 * 2)) #从第四次调用返回

　　5 * (4 * 6) #从第三次呼叫返回

　　5 * 24 #从第二次呼叫返回

　　20 #从第一次呼叫返回

　　这个函数仍然是阶乘(N)。我们试试N=999，N=1000。问题来了。当N=999时可以输出正确答案，但当N=1000时，会出现以下错误：

　　RuntimeError:超过了最大递归深度

　　因此，请记住，默认的Python对可用的递归深度有限制，以避免耗尽计算机的内存。默认值为1000。

　　递归的优点和缺点

　　优势：

　　递归使代码看起来更干净、更优雅。

　　复杂的任务可以通过递归分解成更简单的子问题。

　　使用递归比一些嵌套迭代更容易。

　　缺点：

　　递归逻辑很难调试和跟踪。

　　递归算法效率低。在递归调用的过程中，系统为每一层的返回点和局部量开辟一个栈来存储。太多的递归很容易导致堆栈溢出。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。