python中的递归函数,Python的递归
首先，递归定义
如果函数包含对自身的调用，则该函数是递归的；
递归，在数学和计算机科学中，是指在函数的定义中使用函数本身的方法；
基本要素
基线条件：确定递归何时结束，函数不再调用自身，也称为递归退出；
递归条件：函数调用自身将一个大问题分解成相似的小问题，也称为递归体。
核心理念
每一次递归，整体问题都比原问题小，递归到一定程度就要直接给出结果。
第二，递归思想
递归算法常用于解决结构相似的问题。
所谓结构相似，是指构成原问题的子问题在结构上与原问题相似，可以用相似的方法求解。具体来说，整个问题的解可以分为两部分：第一部分是一些有直接解的特例；第二部分与原问题类似，但规模比原问题小，取决于第一部分的结果。
本质上，递归就是将一个不能或无法解决的大问题转化为一个或几个小问题，然后将这些小问题进一步分解成更小的问题，直到每个小问题都可以直接解决。
实际上，递归会暂时挂起所有之前调用的函数，所有挂起的内容都不会被逆向计算，直到递归终止条件给出明确的结果。实际上，递归也可以看作是一个逆向计算的过程。前面调用递归的过程只列出表达式，终止条件出现后，由后向前计算待定内容，最后将所有结果一起返回。
三、建筑功能
基本情况：递归程序的最低位置，在这里不需要再次操作，可以直接返回一个结果；
所有递归程序必须至少有一个基线条件，并且必须保证最终达到某个基线条件；否则，程序将永远运行，直到程序内存或堆栈空间不足；
基本结构
至少一个基线条件：通常在递归函数开始时，设置基线条件；
一系列规则：每次调用递归函数，它都接近基线条件。
四。基本步骤
初始化算法：递归程序通常需要在开始时使用一个种子值。要完成这个任务，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但是可以设置递归计算的种子值；
检查要处理的当前值是否与基线条件匹配(基本情况)。如果是，则处理并返回值；
用一个更小或更简单的子问题(或多个子问题)重新定义答案；
对子问题运行算法；
将结果组合成答案的表达式；
返回结果。
第五，递归应用
递归算法一般用于解决三类问题。
数据定义是递归定义的，比如斐波那契函数，阶乘等。
问题的求解通过递归算法实现，如：回溯法；
数据结构是递归定义的，如树遍历、图搜索等。
优势
递归使代码看起来更干净、更优雅；
递归可以将复杂的任务分解成更简单的子问题；
使用递归比使用一些嵌套迭代更容易解决问题。
劣势
递归逻辑很难调试和跟进；
递归是低效的。因为在递归调用过程中，系统会开辟一个新的堆栈，供各层的返回值或局部变量存储。太多的递归很容易导致堆栈溢出。
六、经典案例：阶乘
阶乘：fact(n)=n！=1 * 2 * 3 * 4 * .* (n-1) * n=n *事实(n-1)
Fact(n)，可以表示为n * fact(n-1)。只有当n=1时才需要特殊处理；
递归
非递归阶乘实现
定义阶乘(n):
res=1
对于范围(2，n ^ 1)中的I:
res *=i
返回资源
print(阶乘(4))
24
递归阶乘实现
定义阶乘(n):
如果n==0或n==1:
返回1
否则：
return (n *阶乘(n - 1))
print(阶乘(5))
120
递归过程
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 #从第二次呼叫返回
120
Python的默认递归数限制为1000，以避免耗尽计算机内存。
七。尾部递归优化
在计算机中，函数调用是通过栈的数据结构来实现的。每次进入一个函数调用，都会在栈中增加一个栈帧，每次函数返回，都会从栈中减去一个栈帧。因为堆栈的大小不是无限的，过多的递归调用可能会导致堆栈溢出。
递归：指函数返回时调用自身，返回语句不能包含表达式。这样，编译器或解释器就可以优化尾递归，使递归本身无论被调用多少次，都只占用一个堆栈帧，不会出现堆栈溢出。
尾部递归的效果和循环是一样的。实际上，loop可以看作是一种特殊的尾部递归函数。
尾递归是一种优化递归防止溢出的方法，但不能完全解决溢出。举个形象的例子：开车慢可以减少事故，但减速不一定会出事故；
factorial的fact(n)函数，return语句，返回n * fact(n-1)的乘法表达式，不是尾递归。要更改为尾部递归，需要将每一步的乘积传递到递归函数中。
参考代码如下：
定义阶乘(n):
返回fact_iter(n，1)
def fact_iter(n，产品):
如果n==1:
返料
return fact_iter(n - 1，n *乘积)
print(阶乘(5))
120
将每次的乘积保存到乘积中，返回fact_iter(n-1，n * product)只返回函数本身。函数调用前会计算N-1和n *乘积，不会影响函数调用。
优化的本质是通过n * product把原来逆序的计算变成正序的计算，是一种递归的思想，但是不会占用其他栈帧，因为所有的结果都已经存储在product里了。事实(5)对应的fact_iter(5，1)的调用如下：
===fact_iter(5，1)
===fact_iter(4，5)
===fact_iter(3，20)
===fact_iter(2，60)
===fact_iter(1，120)
===120
尾部递归调用时，如果做了优化，堆栈不会增长，无论调用多少次，堆栈都不会溢出。
不幸的是，大多数编程语言都没有针对尾部递归进行优化，Python解释器也是如此。任何递归函数都有堆栈溢出的问题。因此，即使将上述fact(n)函数改为尾递归，也可能导致堆栈溢出。
八。常见算法
斐波那契数列
数列：规定F(0)=0，F(1)=1，从第三项开始，每项等于前两项之和，即F(N)=F(N-1) F(N-2) (N=2)。
参考码
定义斐波那契(n):
如果n 2:
返回
返回斐波纳契(n-1)斐波纳契(n-2)
print(fibonacci(10))
55
n个项目的指定值的总和
s=a * 1 a * 2 a * 3 a * 4.a * n，SSS(a，n)=SSS(a，n-1) a * n
参考码
def n_sum(a，n):
如果n==1:
返回a
返回n_sum(a，n - 1) n * a
print(n_sum(2，5))
30
快速排序
原理：基于分而治之策略，设置一个pivot，将数据与pivot进行比较，分为大于或小于两部分，连续递归、分而治之的方式对数据进行排序；
参考码
定义快速排序(n):
如果len(n) 2:
返回
否则：
枢轴=n[0]
left=[x for x in n[1:] if x pivot]
right=[x for x in n[1:] if x pivot]
return quick_sort(左)[x for x in n if x==n[0]] quick_sort(右)
print(快速排序([5，11，3，5，8，2，6，7，3])
[2, 3, 3, 5, 5, 6, 7, 8, 11]
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。