递归确实是一个比较抽象的数理逻辑，可以简单理解为“程序调用自己的算法”。维基百科对递归的解释是：递归（英文：Recursion），又译为递归，在数学和计算机科学中，是指在函数定义中使用函数本身的方法。术语递归也更常用于描述以自相似的方式重复事物的过程。例如，当两个镜子彼此近似平行时，嵌套在镜子中的图像以无限递归的方式出现。也可以理解为自我复制的过程。“过”是经过的意思，“还”是返回的意思。先一层层传递一个方法，然后传递到最后一层，返回结果。比如我在排队做核酸检测，排在我前面的有100个人。我想问问医护人员几点下班，就问前面的哥，哥再问前面的人，一一传递，最后传给医护人员.在那里，回复说下午六点下班。这句话传了回去，终于传到我这里，我才知道医护人员六点下班了。这个过程是一个递归过程。如果说“传递消息”本身就是一个方法，那么传递消息的整个过程就是在调用自己的方法，最后得到结果。这跟流通不一样，相当于给大家戴上耳机，然后有“中介”会一一询问你知道医护人员什么时候下班，你问医护人员的时候，你就会得到答案，“中介”告诉我六点下班。本质上，递归就是不断地拆解一个大问题，就像剥洋葱一样，最后拆解到最小层次，并返回求解结果。举个Python中最简单的递归函数的例子，说说递归的应用。我们经常看到函数调用自己来实现循环操作，比如计算阶乘的函数。整数n的阶乘为n*(n-1)*(n-2)*...*3*2*1。如下5行Python代码所示，可以实现阶乘的计算。deffact(n):'''n代表所需数的阶乘'''ifn==1:returnnn=n*fact(n-1)returnnprint(factorial(5))很多人可能会混淆this里面的计算逻辑，为什么fact函数会调用自己，最终能得到结果。根据数理逻辑我们可以推导出：整数n的阶乘为：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*factorial(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中，我们可以用一个递归函数来实现斐波那契数列：#1,1,2,3,5,8,13,21,34,55，试着判断第12个数是哪个数列？deffab(n):'''n是斐波那契数列'''如果n<=2:v=1returnvv=fab(n-1)+fab(n-2)returnvprint(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)，命题P(n)对所有自然数n(≥n0)都成立。除了数学上的解释，之前还看到过递归比较形象的解释：1、我们完成了吗？如果完成，返回结果。如果没有这样的终止条件，递归将永远持续下去。2.如果不是，则简化问题，解决更容易的问题，并将结果组合成原问题的解决方案。然后返回到该解决方案。哈哈，到这里是不是对递归有了更深的理解呢？不清楚也没关系，这里递归的案例比较多，用Python实现，可以说是非常简洁了。"最大公因数："defgcd(m,n):ifn==0:returnmelse:returngcd(n,m%n)"1到n的数字总和："defsumnums(n):ifn==1:返回1returnn+sumnums(n-1)print(sumnums(3))"stringreverseorder:"defreverse(string):iflen(string)==0:returnstringelse:returnreverse(string[1:])+string[0]reverseme='我是帅哥'print(reverse(reverseme))"河内塔问题："deftowerOfHanoi(numrings,from_pole,to_pole,aux_pole):ifnumrings==1:print('将环1从',from_pole,'poleto',to_pole,'pole')returntowerOfHanoi(numrings-1,from_pole,aux_pole,to_pole)print('移动环',numrings,'from',from_pole,'poleto',to_pole,'pole')towerOfHanoi(numrings-1,aux_pole,to_pole,from_pole)numrings=2towerOfHanoi(numrings,'Left','Right','Middle')"二分法查找有序列表指定值："data=[1,3,6,13,56,123,345,1024,3223,6688]defdichotomy(min,max,d,n):'''min表示有序列表头索引max表示有序索引在列表末尾表示有序列表n表示要查找的元素'''mid=(min+max)//2ifmid==0:return'None'elifd[mid]
