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

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

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

接下来我们举个例子来帮助理解递归过程，当我们在电影院里想知道自己坐在哪一排，但是前面排数太多了，所以懒得数了。于是就问自己前面的人在哪一排？这样加上 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))

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