Python 遞迴函式
本文章參考自ofollow,noindex">廖雪峰的官方網站
Python--遞迴函式 一. 描述 1.程式語言中, 函式Func(Type a,......)直接或間接呼叫函式本身,則該函式稱為遞迴函式. 2.在數學上,關於遞迴函式的定義如下: 對於某一函式f(x), 其定義域是集合A, 那麼若對於A集合中的某一個值x0, 其函式值f(x0)由f(f(x0))決定,那麼就稱f(x)為遞迴函式. 3.遞迴的定義:一種計算過程, 如果其中每一步都要用到前一步或前幾步的結果, 稱為遞迴的. 用遞迴過程定義的函式, 稱為遞迴函式, 例如連加,連乘及階乘等. 凡是遞迴的函式, 是可計算的, 即能行的. 二. 例項說明 1. 例1: 計算階乘n! = 1 * 2 * 3 * ... * n, 用函式fact(n)表示, 可以看出: fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n, 所以, fact(n)可以表示為n * fact(n-1), 只有n = 1時需要特殊處理. 於是, fact(n)用遞迴的方式寫出來就是:
def fact(n): if n == 1: return 1 return n * fact(n - 1) print(fact(5))# 輸出結果: 120 print(fact(1))# 輸出結果: 1
上面就是一個遞迴函式. 如果我們計算fact(5), 可以根據函式定義看到計算過程如下: ==> fact(5) ==> 5 * fact(4) ==> 5 * (4 * fact(3)) ==> 5 * (4 * (3 * fact(2))) ==> 5 * (4 * (3 * (2 * fact(1)))) ==> 5 * (4 * (3 * (2 * 1))) ==> 5 * (4 * (3 * 2)) ==> 5 * (4 * 6) ==> 5 * 24 ==> 120 遞迴函式的優點是定義簡單, 邏輯清晰. 理論上, 所有的遞迴函式都可以寫成迴圈的方式, 但迴圈的邏輯不如遞迴清晰. 使用遞迴函式需要注意防止棧溢位. 在計算機中, 函式呼叫是通過棧(stack)這種資料結構實現的,每當進入一個函式呼叫, 棧就會加一層棧幀, 每當函式返回, 棧就會減少一層棧幀. 由於棧的大小不是無限的, 所以, 遞迴呼叫的次數過多, 會導致 棧溢位. 當嘗試呼叫fact(1000)時, 程式會報錯. 總結來說,使用遞迴函式的優點是邏輯簡單清晰, 缺點是過深的呼叫會導致棧溢位(即比較佔用記憶體空間). 2. 例2:用遞迴函式來實現對樹形結構的遍歷是一種很好的方法! 以下例項為遍歷某資料夾內的所有檔案和資料夾:
import os# 引入os模組 def func(file_path, ceng): # 獲取到路徑下的所有檔案 lst = os.listdir(file_path)# 得到資料夾裡的所有檔案和資料夾 for file in lst:# 遍歷資料夾 full_path = os.psth.join(file_path, file)# 獲取到檔案的全路徑 if os.path.isdir(full_path):# 判斷這個路徑是否是一個資料夾 print("\t" * ceng, file) func(full_path, ceng + 1) else: print("\t" * ceng, file) else: return func("D:\Program Files\\feiq\Recv Files", 0) # 具體檔案路徑可以根據自己的實際情況進行修改
總的來說, 遞迴函式的實質就是自己呼叫自己. 在下一次對自己的呼叫之前, 函式把引數值根據某種對應法則進行了改變, 從而將改變後的引數作為下一次呼叫的引數. 以上面的例子來說, 函式func的形參從(file_path, ceng)變成了(full_path, ceng + 1). 所以, 我們在使用遞迴函式時, 一定要明確,什麼是不變的(函式本身), 什麼是變的(引數) .