python递归案例,递归法Python
递归(英文：Recursion)，也译为递归，是指数学和计算机科学中在函数的定义中使用函数本身的方法。递归也常用来描述通过自相似重复事物的过程。本文将详细介绍Python中的递归算法，有需要的可以参考一下。
递归是一种抽象的数学逻辑，可以简单理解为“程序调用自己的算法”。
维基百科对递归的解释是：
递归(英文：Recursion)，也译为递归，是指数学和计算机科学中在函数的定义中使用函数本身的方法。递归也常用来描述通过自相似重复事物的过程。
例如，当两个镜像近似平行时，镜像中的嵌套图像以无限递归的形式出现。也可以理解为一个自我复制的过程。
‘传’是传的意思，‘回’是回的意思。首先，一层一层地传递一个方法，然后传递到最后一层，返回结果。
比如我排队等核酸检测的时候，前面有100个人。我想问医护人员什么时候下班，就问了前面的那位兄弟。他又问了前面的人，一个一个传过去，最后传给医护人员。他回答说下午六点下班。这句话又传了回来，最后传到我这里。我知道医务人员六点就下班了。
这个过程是一个递归的过程。如果‘消息传递’本身就是一个方法，那么整个消息传递过程就是在调用自己的方法，最终得到结果。
这和流通不一样。循环相当于给每个人戴上耳机，然后一个‘中介’一个个问你知不知道医护人员几点下班。当你问医务人员时，你会得到一个答案。‘中介’告诉我六点下班。
递归本质上就是不断拆解一个大问题，就像剥洋葱一样，最后拆解到最小的层次，就会返回解决问题的结果。
举一个Python中最简单的递归函数的例子，谈谈递归的应用。
我们经常看到函数会调用自己来实现循环运算，比如求阶乘的函数。
整数的阶乘是n*(n-1)*(n-2)*.*3*2*1.
比如下面五行Python代码就可以实现阶乘的计算。
定义事实(n):
n代表所需数字的阶乘
ifn==1:
returnn
n=n *事实(n-1)
returnn
print(阶乘(5))
输出：
120
很多人可能会对这里的计算逻辑感到困惑，为什么事实函数会调用自己，最后得到结果。
我们可以根据数理逻辑推导出：
整数的阶乘是：fact(n)=n*(n-1)*.*3*2*1.
整数n-1的阶乘是：fact (n-1)=(n-1) * (n-2) *.* 3 * 2 * 1.
因此，可以推断出fact(n)=n*fact(n-1)
有没有一个事实方法可以对每一个数都调用，最后调用n=1时，返回结果n的阶乘？
上图可以看到，递归函数会一层一层向下调用，最后当n=1时，结果会向上返回。
这就是递归的整个过程。如果我们给递归下一个准确的定义，可以概括为以下三点：
1.至少有一个确定的递归结束条件；
2.给出递归终止时的处理方法；
3.每进入一次更深的递归，问题的规模(计算量)都要比上一次递归减少。
以上面的代码为例：
deffactorial(n):
n代表所需数字的阶乘
Ifn==1:# 1，定义递归终止条件；
Returnn#2，递归终止的处理方法
N=n *阶乘(n-1)#遍
Returnn# Return
除了常见的阶乘情况，还有斐波那契数列，这也是递归的经典用法。
斐波纳契数列：1，1，2，3，5，8，13，21，34，55，89.
这个序列从第三项开始，每一项都等于前两项之和。
递归定义如下：F(0)=0，F(1)=1，F(n)=F(n-1) F(n-2)(n 2，n N*)
在Python中，我们可以用递归函数来实现斐波那契数列：
/p>
# 1，1，2，3，5，8，13，21，34，55，试判断数列第12个数是哪个？def fab(n):
n为斐波那契数列
if n <= 2:
v = 1
return v
v = fab(n-1)+fab(n-2)
return v
print(fab(12))
使用数学方法进行推导：
- fab(0) = 0（初始值）
- fab(1) = 1（初始值）
- 对所有大于1的整数n：fab(n) = fab(n-1)+ fab(n-2)（递归定义）
其实以上两个递归的案例都可以用数学归纳法来解释，就是高中数学的知识。
一般地，证明一个与自然数n有关的命题P(n），有如下步骤：
（1）证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况；
（2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。
综合（1）（2），对一切自然数n（≥n0），命题P(n）都成立。
除了数学的解释，之前也看到有人对递归更加形象的解释：
1、我们已经完成了吗？如果完成了，返回结果。如果没有这样的终止条件，递归将会永远地继续下去。
2、如果没有，则简化问题，解决较容易的问题，并将结果组装成原始问题的解决办法。然后返回该解决办法。
哈哈,到这里大家是不是对递归有了一个更加深刻的认识。
如果还不清楚，没关系，这里还有更多的递归案例，用Python来实现，可以说非常简洁。
「最大公因数：」
def gcd(m, n):if n == 0:
return m
else:
return gcd(n, m%n)
「从 1 到 n 的数字之和：」
def sumnums(n):if n == 1:
return 1
return n + sumnums(n - 1)
print(sumnums(3))
「字符串倒序：」
def reverse(string):if len(string) == 0:
return string
else:
return reverse(string[1:]) + string[0]
reverseme = 我是帅哥
print(reverse(reverseme))
「汉诺塔问题：」
def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):if numrings == 1:
print(Move ring 1 from, from_pole, pole to, to_pole, pole)
return
towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
print(Move ring, numrings, from, from_pole, pole to, to_pole, pole)
towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)
numrings = 2
towerOfHanoi(numrings, Left, Right, Middle)
「二分法找有序列表指定值：」
data = [1,3,6,13,56,123,345,1024,3223,6688]def dichotomy(min,max,d,n):
min表示有序列表头部索引
max表示有序列表尾部索引
d表示有序列表
n表示需要寻找的元素
mid = (min+max)//2
if mid==0:
return None
elif d[mid]<n:
print(向右侧找！)
return dichotomy(mid,max,d,n)
elif d[mid]>n:
print(向左侧找！)
return dichotomy(min,mid,d,n)
else:
print(找到了%s%d[mid])
return
res = dichotomy(0,len(data),data,222)
print(res)
有位大佬说过：To Iterate is Human, to Recurse, Divine.
中文译为：人理解迭代，神理解递归。
可见递归是非常神奇的算法，它的神奇之处在于它允许用户用有限的语句描述无限的对象。
当然人无完人，递归也是有缺点的，它一般效率较低，且会导致调用栈溢出。
因为递归不断调用自身函数，且产生大量变量，而栈空间的容量是有限的，循环太多就会效率低下，甚至导致调用栈溢出
以上就是Python实例详解递归算法的详细内容，更多关于Python递归算法的资料请关注盛行IT软件开发工作室其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。