递归算法是一种直接或间接调用自身函数或者方法，直到某个条件（也称为终止条件或基线条件） 匹配的算法。

递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。定义看起来太深，通俗点说，只要一个方法（函数）里面调用了自身，这个方法就用到了递归算法。但是这里还有一个条件，就是在使用递归时，还必须有一个明确的递归结束条件，称为递归出口，否则理论上会永远持续下去，一遍又一遍地调用自己，没有任何返回。

那么究竟什么是调用自身？举个例子，我们经常会听大人讲这样一个故事，“从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说，从前有座山，山里有座庙，庙里有个老和尚”。只要不加以限制，这个故事可以一直讲下去，就好比递归中的调用自身，只是在缺少了递归终止条件，没有出口，无限循环。

接下来我们举个例子来帮助理解递归过程，当我们在电影院里想知道自己坐在哪一排，但是前面排数太多了，所以懒得数了。于是就问自己前面的人在哪一排？这样加上 1 就是自己在的排数了，没想到的是前面的人和自己一样懒，他又问他前面的人在哪一排，巧的是整个电院的人都很懒，直到第一排的人说我是第一排，然后从第二排的人开始向后面的人传达信息，最后这一列的人包括自己就知道自己在哪一排了。在这个过程中第一排的人就是递归出口，他需要给一个确切的数字 1，其他人才知道自己在哪，而递归的最终结果是从递归出口倒推出来的。

在程序设计中使用递归算法通常需要定义递归函数， 通过对该函数的调用来获得最终解。

递归函数都必须有两个条件组成： 基线条件（终止条件）和递归条件。 符合基线（终止条件）条件终止函数调用， 符合递归条件则函数继续调用自己。

「递归函数基本结构：」

def 函数名(参数1,参数2,……): if 条件表达式: # 终止条件 语句 return 值（或表达式） # 可省略 else: # 递归条件 函数名(参数1,参数2,……)

「递归的优点：」

避免不必要的函数调用。以比使用复杂的迭代循环更简单的方式解决问题。使用递归可以轻松编写复杂的程序。

「递归的缺点：」

太多的递归函数可能会混淆代码。递归解决方案是合乎逻辑的，并且不容易调试和理解。由于函数调用，程序执行速度变慢，并且需要一些时间才能返回值。

「递归的类型：」

直接递归。间接递归。示例：计算阶乘

我们自定义函数 fact()，计算7的阶乘7!，即fact(7)。

7!= 1*2*3*4*5*6*7 = 5040

根据递归原理，将大的问题分解成同类子问题。

fact(7)可以分解为7乘以fact(6)，fact(6)可以分解为6乘以fact(5)，直到经过多次分解把问题转化为有直接解法的特殊情况：fact(1),fact(1)即1的阶乘，结果为1。得到解后再回归到更大问题求解，最终得到较大或更大问题的答案。

「求解过程：」

fact(7)

=7* fact(6)

=7*(6*fact(5))

=7*(6*(5*fact(4)))

=7*(6*(5*(4*fact(3))))

=7*(6*(5*(4*(3*fact(2)))))

=7*(6*(5*(4*(3*(2*fact(1))))))

def fact(n): #自定义函数 if n==1: #终止条件 return 1 #结束递归 else: #递归条件 f=n*fact(n-1) #调用递归 return f #返回乘积#主程序print("m=",fact(7)) #调用递归斐波那契数列

斐波那契数列是 0， 1， 1， 2， 3， 5， 8 …… 的整数序列。从第三个数开始，数值是前两个数字之和。

终止条件：f(0)=0，f(1)=1

递归条件：f(n)=f(n-1)+f(n-2)

def fib(n): if n <= 1: #终止条件 return n #结束递归 else: #递归条件 return fib(n-1) + fib(n-2) #调用递归 # 主程序for i in range(6): print(fib(i))

❝

文章创作不易，如果您喜欢这篇文章，请关注、点赞并分享给朋友。如有意见和建议，请在评论中反馈！

❞