Python遞歸函數的原理及應用

本篇內容主要講解“Python遞歸函數的原理及應用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Python遞歸函數的原理及應用”吧!

一、什么是遞歸函數?

在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數。

二、函數的遞歸調用原理

實際上遞歸函數是在棧內存上遞歸執行的，每次遞歸執行一次就會耗費一些棧內存。

棧內存的大小是限制遞歸深度的重要因素

三、案例分析

1.求階乘

計算階乘n! = 1 x 2 x 3 x … x n，

可以用函數fact(n)表示。

fact(n) = n! = 1 x 2 x 3 x … x (n-1) x n = (n-1)! x n = fact(n-1) x n

fact(n)可以表示為n x fact(n-1)，只有n=1時需要特殊處理。

于是，fact(n)用遞歸的方式寫出來就是：

def fact(n):     if n == 1:         return 1     return n * fact(n - 1)

如果計算fact(6)，可以根據函數定義看到計算過程如下：

def fac(n):     if n==1:         return 1     else:         res=n*fac(n-1)         return  res  print(fac(6))

運行結果：

2.斐波拉契級數

有這樣一個數列：1，1，2，3，5，8，13，21，34…。其第一元素和第二個元素等于 1，其他元素等于其前面兩個元素的和。

例：

def fab(n):  # 定義斐波拉契級數     if n in [1, 2]:  # 如果n=1或者2       return 1     return fab(n - 1) + fab(n - 2)  # n>2   print(fab(1))  # 斐波拉契級數的第一個元素  print(fab(2))  # 斐波拉契級數的第二個元素  print(fab(8))  # 斐波拉契級數的第8個元素 print(fab(13))  # 斐波拉契級數的第9個元素

運行結果：

3.遞歸函數的優點

定義簡單，邏輯清晰。理論上，所有的遞歸函數都可以寫成循環的方式，但循環的邏輯不如遞歸清晰。

遞歸需要注意遞歸的深度。由于遞歸會產生多次函數調用，而函數調用會消耗代碼的棧空間，如果遞歸的深度太大，會導致棧溢出。以上面的階乘為例，如果計算  100000 的階乘，在一般機器上都會出現棧溢出的問題。

print(fac(10000))

如下所示：

四、總結

本文基于Python基礎。Python標準的解釋器沒有針對尾遞歸做優化，任何遞歸函數都存在棧溢出。介紹了在使用遞歸函數的優缺點，優點是邏輯簡單清晰，缺點是過深的調用會導致棧溢出。

在實際案例中，針對尾遞歸優化的語言可以通過尾遞歸防止棧溢出。尾遞歸事實上和循環是等價的，沒有循環語句的編程語言只能通過尾遞歸實現循環，進行詳細的講解。

到此，相信大家對“Python遞歸函數的原理及應用”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！