什么是遞歸函數(shù)

一種計算過程，如果其中每一步都要用到前一步或前幾步的結(jié)果年栓，稱為遞歸的韵洋。用遞歸過程定義的函數(shù)，稱為遞歸函數(shù)食拜，例如連加负甸、連乘及階乘等呻待。凡是遞歸的函數(shù)队腐，都是可計算的，即能行的迫淹。

• 遞歸就是一個函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身敛熬。

編程語言中的對遞歸定義:

• 編程語言中应民，函數(shù)Func(Type a,……)直接或間接調(diào)用函數(shù)本身诲锹，則該函數(shù)稱為遞歸函數(shù)。遞歸函數(shù)不能定義為內(nèi)聯(lián)函數(shù)改备。

數(shù)學中對遞歸的定義:

• 在數(shù)學上悬钳，關于遞歸函數(shù)的定義如下：對于某一函數(shù)f(x)默勾，其定義域是集合A母剥，那么若對于A集合中的某一個值X0形导，其函數(shù)值f(x0)由f(f(x0))決定朵耕，那么就稱f(x)為遞歸函數(shù)。

遞歸的條件:

• 一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)伪阶，在上面的例子中能夠看出栅贴，它必須滿足以下兩個條件：
  • 1）執(zhí)行遞歸函數(shù)將反復調(diào)用其自身熏迹，每調(diào)用一次就進入新的一層注暗。
  • 2）必須有結(jié)束條件,即必須有一個終止處理或計算的準則友存。

遞歸函數(shù)的應用

應用一: 計算階乘(factorial)

• 定義:一個正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積屡立，并且0的階乘為1膨俐。自然數(shù)n的階乘寫作n!

• 任何大于等于1 的自然數(shù)n 階乘表示方法：n! = 1*2*3* ...*(n-1)*n,或,n! = n *(n-1)!

• 階乘的規(guī)律:

  1! = 1
  2! = 2 × 1 = 2 × 1!
  3! = 3 × 2 × 1 = 3 × 2!
  4! = 4 × 3 × 2 × 1 = 4 × 3!
  ...
  n! = n × (n-1)!
  

• 用遞歸函數(shù)來計算階乘: 通過用戶輸入數(shù)字(n)計算階乘

  # 獲取用戶輸入的數(shù)字
  num = int(input("請輸入一個數(shù)字: "))
  factorial = 1
  
  # 查看數(shù)字是負數(shù)敛摘，0 或 正數(shù)
  if num < 0:
      print("抱歉乳愉，負數(shù)沒有階乘")
  elif num == 0:
      print("0 的階乘為 1")
  else:
       for i in range(1,num + 1):
          factorial = factorial*I
  
  print("%d 的階乘為 %d" %(num,factorial))
  

• 上述代碼運行結(jié)果如下:

  請輸入一個數(shù)字: 3   #輸入3,求3的階乘. 3! = 3*2*1 =6
  3 的階乘為 6
  

-上述遞歸函數(shù)的調(diào)用過程:

遞歸函數(shù)階乘3的調(diào)用.png

• 在Python中,還可以使用循環(huán)來實現(xiàn)階乘的計算:

  • 使用while循環(huán)實現(xiàn)計算3的階乘

  n=4      #求4的階乘
  result=1
  I=1
  while i<=4:
    result=result*I
    I+=1
  
  print(result)
  

從上面兩中方法的對比可以看出捕虽，遞歸函數(shù)的作用和循環(huán)的方法效果一樣泄私，即遞歸函數(shù)本質(zhì)上是一個方法的循環(huán)調(diào)用晌端，注意：有可能會出現(xiàn)死循環(huán)咧纠。因此惧盹，使用遞歸函數(shù)時瞪讼，一定要定義遞歸的邊界（即什么時候退出循環(huán)）符欠。

應用二: 計算斐波那契數(shù)列 (Fibonacci sequence)

• 斐波那契數(shù)列（Fibonacci sequence）希柿，又稱黃金分割數(shù)列诊沪、因數(shù)學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”曾撤，指的是這樣一個數(shù)列：
  • 1端姚，1，2挤悉，3渐裸，5，8，13昏鹃，21尚氛，34，55洞渤，89阅嘶，144……
  • 從3三個數(shù)開始,后一個數(shù)等于前面兩個數(shù)的和
  • 在數(shù)學上讯柔，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0捏卓，F(xiàn)1=1遥金，F(xiàn)n=F(n-1)+F(n-2)（n>=2冲粤，n∈N*）

斐波那契數(shù)列_兔兔的繁殖.jpg

• 用遞歸函數(shù)來實現(xiàn)獲取斐波拉契數(shù)列中第n個數(shù)字的值:

  #  計算斐波那契數(shù)列第n位的值
  def fab(n):
      if n > 2:
          return fab(n-1) + fab(n-2)
      else:
          return 1
  
  #  打印斐波那契數(shù)列
  def printfablist(n):
      for i in range(1, n+1):
          print(fab(i),end = ' ')
  
  # 傳參調(diào)用
  printfablist(int(input('請輸入要輸出多少項：')))
  

• 上述代碼運行結(jié)果如下:

  請輸入要輸出多少項：4    #鍵入4,求斐波那契數(shù)列前四項
  1 1 2 3   # 得到斐波那契數(shù)列前四項
  

• 同樣的,除了遞歸函數(shù)外,還可以使用while循環(huán)來實現(xiàn)斐波那契數(shù)列:

  # 獲取用戶輸入數(shù)據(jù)
  num_n = int(input("請輸入你需要幾項:"))
  
  # 第一和第二項
  n1 = 1
  n2 = 1
  count = 2
  
  # 判斷輸入的值是否合法
  if num_n <= 0:
      print("請輸入一個正整數(shù)。")
  elif num_n == 1:
      print("斐波那契數(shù)列：")
      print(n1)
  else:
      print("斐波那契數(shù)列：")
      print(n1,",",n2,end=" , ")
      while count < num_n:
          nth = n1 + n2
          print(nth,end=" , ")
          # 更新值
          n1 = n2
          n2 = nth
          count += 1
  

• 上述代碼運行結(jié)果如下:

  請輸入你需要幾項:4  #鍵入4,求斐波那契數(shù)列前四項
  斐波那契數(shù)列：
  1 , 1 , 2 , 3 ,     # 得到斐波那契數(shù)列前四項
  

從上面兩中方法的對比可以看出，遞歸函數(shù)的作用和循環(huán)的方法效果一樣哩都，即遞歸函數(shù)本質(zhì)上是一個方法的循環(huán)調(diào)用，注意：有可能會出現(xiàn)死循環(huán)。因此，使用遞歸函數(shù)時章钾，一定要定義遞歸的邊界（即什么時候退出循環(huán)）府寒。

以上兩個案例是遞歸函數(shù)的經(jīng)典案例，需要記住其使用方法。==循環(huán)能干的事,遞歸都能干;遞歸能干的循環(huán)不一定能干==

遞歸函數(shù)特點

遞歸：自我調(diào)用且有完成狀態(tài)炮姨。

1. 每一級函數(shù)調(diào)用時都有自己的變量拄查，但是函數(shù)代碼并不會得到復制碍脏，如計算5的階乘時每遞推一次變量都不同糊探；

2. 每次調(diào)用都會有一次返回姜性，如計算5的階乘時每遞推一次都返回進行下一次；

3. 遞歸函數(shù)中，位于遞歸調(diào)用前的語句和各級被調(diào)用函數(shù)具有相同的執(zhí)行順序豌研；

4. 遞歸函數(shù)中，位于遞歸調(diào)用后的語句的執(zhí)行順序和各個被調(diào)用函數(shù)的順序相反；

5. 遞歸函數(shù)中必須有終止語句房铭。

遞歸函數(shù)的缺點: 過深的調(diào)用會導致棧溢出

遞歸函數(shù)的優(yōu)點是定義簡單凌蔬，邏輯清晰蛇耀。理論上抠忘，所有的遞歸函數(shù)都可以寫成循環(huán)的方式伯顶，但循環(huán)的邏輯不如遞歸清晰谭网。

使用遞歸函數(shù)需要注意防止棧溢出。在計算機中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，每當進入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當函數(shù)返回葱椭，棧就會減一層棧幀踱侣。由于棧的大小不是無限的待榔，所以姿骏，遞歸調(diào)用的次數(shù)過多，會導致棧溢出。

• 使用python寫的遞歸程序如果遞歸太深, 那么極有可能因為超過系統(tǒng)默認的遞歸深度限制而出現(xiàn)
  • 例如使用遞歸計算階乘時,傳入?yún)?shù)值1000來調(diào)用函數(shù)factoria(1000),運行會報錯:

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "<stdin>", line 4, in factoria
 ...
 File "<stdin>", line 4, in factoria
RuntimeError: maximum recursion depth exceeded

• 解決上述報錯問題的方法很簡單, 人為將系統(tǒng)設定的遞歸深度設置為一個較大的值即可:

  import sys
  sys.setrecursionlimit(1000000) #括號中的值為遞歸深度
  

參考資源:

• 博客園:遞歸函數(shù)的定義和幾個小例子
• CSDN:什么是遞歸函數(shù)
• 廖雪峰老師的博客
• 解決python遞歸棧溢出