递归算法是一种直接或间接调用自身函数或者方法，直到某个条件（也称为终止条件或基线条件） 匹配的算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。定义看起来太深，通俗点说，只要一个方法（函数）里面调用了自身，这个方法就用到了递归算法。但是这里还有一个条件，就是在使用递归时，还必须有一个明确的递归结束条件，称为递归出口，否则理论上会永远持续下去，一遍又一遍地调用自己，没有任何返回。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
那么究竟什么是调用自身？举个例子，我们经常会听大人讲这样一个故事，“从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说，从前有座山，山里有座庙，庙里有个老和尚”。只要不加以限制，这个故事可以一直讲下去，就好比递归中的调用自身，只是在缺少了递归终止条件，没有出口，无限循环。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
接下来我们举个例子来帮助理解递归过程，当我们在电影院里想知道自己坐在哪一排，但是前面排数太多了，所以懒得数了。于是就问自己前面的人在哪一排？这样加上 1 就是自己在的排数了，没想到的是前面的人和自己一样懒，他又问他前面的人在哪一排，巧的是整个电院的人都很懒，直到第一排的人说我是第一排，然后从第二排的人开始向后面的人传达信息，最后这一列的人包括自己就知道自己在哪一排了。在这个过程中第一排的人就是递归出口，他需要给一个确切的数字 1，其他人才知道自己在哪，而递归的最终结果是从递归出口倒推出来的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
在程序设计中使用递归算法通常需要定义递归函数， 通过对该函数的调用来获得最终解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
递归函数都必须有两个条件组成：基线条件（终止条件）和递归条件。符合基线（终止条件）条件终止函数调用， 符合递归条件则函数继续调用自己。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
「递归函数基本结构：」文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
def 函数名(参数1,参数2,……):
if 条件表达式: # 终止条件
语句
return 值（或表达式） # 可省略
else: # 递归条件
函数名(参数1,参数2,……)
「递归的优点：」文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
避免不必要的函数调用。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html 以比使用复杂的迭代循环更简单的方式解决问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html 使用递归可以轻松编写复杂的程序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
「递归的缺点：」文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
太多的递归函数可能会混淆代码。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html 递归解决方案是合乎逻辑的，并且不容易调试和理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html 由于函数调用，程序执行速度变慢，并且需要一些时间才能返回值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
「递归的类型：」文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
直接递归。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html 间接递归。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
示例：计算阶乘
我们自定义函数 fact()，计算7的阶乘7!，即fact(7)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
7!= 1*2*3*4*5*6*7 = 5040文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
根据递归原理，将大的问题分解成同类子问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
fact(7)可以分解为7乘以fact(6)，fact(6)可以分解为6乘以fact(5)，直到经过多次分解把问题转化为有直接解法的特殊情况：fact(1),fact(1)即1的阶乘，结果为1。得到解后再回归到更大问题求解，最终得到较大或更大问题的答案。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
「求解过程：」文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
fact(7)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7* fact(6)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7*(6*fact(5))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7*(6*(5*fact(4)))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7*(6*(5*(4*fact(3))))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7*(6*(5*(4*(3*fact(2)))))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
=7*(6*(5*(4*(3*(2*fact(1))))))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
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 …… 的整数序列。从第三个数开始，数值是前两个数字之和。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
终止条件：f(0)=0，f(1)=1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
递归条件：f(n)=f(n-1)+f(n-2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/49137.html
def fib(n):
if n <= 1: #终止条件
return n #结束递归
else: #递归条件
return fib(n-1) + fib(n-2) #调用递归
# 主程序
for i in range(6):
print(fib(i))