斐波那契数列 - Python 中的递归算法

递归算法是直接或间接调用自己的函数或方法，直到满足某个条件（也称为终止条件或基本条件）为止的算法。

递归算法的本质是将问题划分为相同类型的子问题，减小子问题的规模，然后递归调用方法来表示问题的解。递归算法对于解决许多问题效率很高，因此算法简洁且易于理解。这个定义似乎太深奥了。通俗地说，只要一个方法（函数）调用了自身，这个方法就采用了递归算法。但这里还有一个条件，那就是在使用递归的时候，还必须有一个明确的递归结束条件，这就是所谓的递归退出，否则理论上会永远持续下去，一次又一次地调用自己，没有任何回报。

那么你到底怎么称呼自己呢？例如，我们经常听到大人讲这样的故事：“从前有一座山，山里有一座寺庙，寺庙里有一个老和尚。老和尚对小和尚说。”从前有一座山，山里有一座寺庙，里面住着一个老和尚。只要没有约束，这个故事就可以继续下去，就像递归中的寻址一样，但是没有递归的终止条件，就没有出口，是一个无限循环。

我们举个例子来理解一下递归过程。当我们在电影院里，我们想知道自己坐在哪一排，但是前面的排太多了，我们懒得数。我问自己，前面的人是哪排？加1就是他所在的数字。他没想到眼前这个人竟然和他一样懒。巧合的是，电子医院里的每个人都很懒，直到第四排的人说我在第一排，然后第二排的人开始向人们传递信息。最后，那一排的人，包括我，都知道自己在哪一排了。这个过程中第一个排队的人就是递归出口。你必须指定一个确切的数字1，以便其他人知道他们在哪里，并且递归的最终结果将从递归出口得出。

在编程中使用递归算法通常需要定义一个递归函数并调用该函数以获得最终的解决方案。

递归函数必须由两个条件组成：基本条件（结束条件）和递归条件。如果满足基线（关闭条件），则函数调用将中止。如果满足递归条件，则函数继续调用自身。

「递归函数的基本结构：」

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

「递归的优点：」

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

『递归的缺点：』

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

「递归类型：」

• 直接递归。
• 间接递归。

示例：阶乘计算

fact() 函数被定制为计算 7 的阶乘！ 7，即事实(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))

(6*=5)*事实 (4)))

=7*(6*(5*(4*事实(3))))

=7*(6*(5*(4*(3*事实(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))