[转载] Python 递归 深入理解递归 Python递归剖析，绝对让你看懂！
參考鏈接： Python | print()中的結束參數
目錄
?遞歸剖析 遞歸的兩個過程 return 返回值 詳解
? ? 遞歸思路二分法和遞歸尾遞歸遞歸練習題
??
?
?
?
遞歸剖析?
遞歸真的很重要，之前學的時候，學的一知半解，以為真正了解，每次想到遞歸，就記得一句：返回給函數的調用者，嗯？函數調用者，你是說外部，還是內部啊？疑問太多了，還有就是被告知一句：遞歸能解決的問題，循環都能解決，所以就更加不重視遞歸了！直到接觸算法后，在解決問題時，最快，最容易理解的解法就是遞歸，但是此時的遞歸卻是看不太懂為什么要這樣做！我先來說下，在算法中遇到可以用遞歸輕松完成的：希爾排序、歸并排序、快速排序、反轉鏈表及各種反轉問題、二叉樹的深度遍歷、二叉樹的各種題基本可以用、全排列…還有算法步驟里需要用到，太多了，所以，遞歸非常重要！“To iterate is human, to recurse divine 迭代是人，遞歸是神”，接下來，我也是看了很多算法書和視頻，重點來整理下遞歸！?
?遞歸的兩個過程?
首先“遞歸”包括兩個過程：遞“去”的過程，“歸”回的過程！先從一個簡單的遞歸函數講起?
def di_gui(n):
? ? print(n, "<===1====>")
? ? if n > 0:
? ? ? ? di_gui(n - 1)
? ? print(n, '<===2====>')
?
?
di_gui(5) # 外部調用后打印的結果是？
?
?遞歸的執行過程：首先，遞歸會執行“去”的過程，只需要滿足終止條件，就會一直在函數內，帶著更新的參數，調用函數自身，注意：到內部調用函數， 以下面的代碼不會被執行，而是暫停阻塞；此時 隨著函數每調用一次自身，還沒有觸發 返回值和到達終止條件，等同于在原來的基礎上不斷“向下/向內”開辟新的內存空間，記住，每次調用一次函數，就不是處在同一空間（想象下《盜夢空間》里的情景，夢中夢，都是處于不同的空間）? ?什么時候“遞”去的過程結束？記住有兩種情況>>> 一是：當前這層空間函數全部執行結束（終止條件），二是：執行到了return 返回值，直接返回；? 重點來理解下，首先是一，看上面的列子，例子中沒有return，但是不斷的調用后，最終還是停止了，因為最后n=0時，di_gi(0)還是去調用，從上往下執行時，遇到if n>0 它被終止了，走不下去了，表明，自己能到達的這層空間已經全部執行完畢；接下來請原地返回吧，返回到哪里？返回到函數的調用者，好我們返回到 di_gui(0)，把“到內部調用函數” 以下的代碼全部執行完；執行完，看代碼走到末尾，以為走出了最外層函數？注意了，此時它所處的空間并不是最外層哦，因為之前它被調用就在空間里面，所以回到的是 di_gui(1)的這一層空間，現在才是真正的開始“回”，所以繼續把di_gui(1)的這一層空間，“到內部調用函數”以下的代碼全部執行完，回到di_gui(2)的這一層空間…直到到達最開始 從外部調用，讓參數5進入的最外層空間位置，才走出來！表示《盜夢空間》里，柯布醒了！? 回來看下，代碼輸出的結果：5 4 3 2 1 00 1 2 3 4 5 （ 注意00這兩個是在同一層空間哦）? ?從內存角度（本質）來分析：每調用一次函數，都會單獨開辟一份棧幀空間，遞歸函數就是不停的開辟和釋放棧幀空間的過程，具體來理解下：一個普通函數從執行到結束，就是一個開辟空間和釋放空間的過程；而遞歸函數是在調用最外層函數時，先開辟一個最外層空間，每調用一次自身，就會在最外層空間內，再自己開辟本次的空間（所以遞歸耗內存）（還有一種說法是，不斷的本次空間的基礎上再開辟空間，等于是不斷的嵌套，其實這兩種說法本質上是一樣的，因為信息都可以做到不共享），空間之間如果不通過參數傳遞或者用return 返回值，信息是不共享的，如下圖↓↓↓??
??
?遞歸的數據共享情況：遞歸每一層間的數據是獨立的，不共享，但是可以通過參數或者返回值來形成共享，參數具體在傳入的是“引用類型”（比如列表）? 遞歸 必須要有一個出口，如果沒有出口就會重復調用，不斷的開辟棧幀空間??
# 獲取最大遞歸層數：
import sys
res=sys.getrecursionlimit()
print(res) # 結果：1000
# sys.setrecursionlimit(800) 可以自己設置最大遞歸層數
?
解釋含有 return 返回值的遞歸，記住 return的返回流程是：先計算，再返回 ，來看下一段求階乘的代碼：?
def jie_cheng(n):
? ? if n <= 1:
? ? ? ? return 1
? ? return n * jie_cheng(n - 1)
? ??
print(jie_cheng(5))
?
?
return 是返回到函數調用者，遞歸函數和普通函數也是一樣的，所以遞歸最后一層空間走到盡頭（一是：指向完畢，二是：遇到return，回顧一下而已）遇到return，就要開始返回了，返回到它的調用者（即是阻塞的位置），直到回到最外層空間如果上面的內容看懂了的話，試著解析下：下面這段代碼的執行流程?
def get_num(num):
? ? if num > 2:
? ? ? ? get_num(num - 1)
? ? print(num)
?
?
get_num(4) # 輸出結果為：2 3 4
?
?
?
?代碼變化一下：?
?
def get_num(num):
? ? if num > 2:
? ? ? ? get_num(num - 1)
? ? else:
? ? ? ? print(num)
?
?
get_num(4) # 輸出結果為 2
?
'''
解析一下：加了else后，首先代碼區有兩個分支，
在num>2時，執行會有遞歸，當n=4 是開辟一層空間；
n=3時開辟一層空間，此時 get_num(2) 再開辟一個空間，
當它從上往下執行過程中，在他本層空間遇到if num>2 不成立，所以走分支 else，直接打印出來；
此時代碼還沒結束，回到上一層空間，num=3, num>2 已經進入了if 不會走else，
num=4 也不會走else，所以這兩層空間沒有值輸出！
'''
?
?return 返回值 詳解?
上面這一大部分，就算是遞歸入門了，接下來才剛剛開始哦！還要繼續講 return ；先來看下這幾段代碼：求全排列的一部分遞歸代碼，試著分別寫出運行結果，并依次分析原因↓↓↓?
# 例1：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? remain = fullpermutation(list[1:])
? ? print(remain)
?
?
print(fullpermutation([1, 2, 3]))??
'''
輸出結果為：
[[3]]
None
None
'''
?
遞歸只會在兩種情況下觸發“回”的過程，上述是在最后一層空間是碰到了return，所以給回到它的調用處（阻塞處），因為return會給調用者返回一個值，所以在本層空間，remain接收到了一個值：[[3]]；接著執行下面的代碼，即是打印remain，所以輸出“[[3]]”，執行完print，等于回到了上一層空間，又到了調用處（阻塞處），那么這層空間還有返回值嗎？答案是沒有，所以“最后一層空間是碰到了return 給它返回的值 只會給最后一層使用”，所以接下來兩層都是打印空！?
# 例2：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? return fullpermutation(list[1:])
?
?
print(fullpermutation([1, 2, 3]))
'''
輸出結果為：
[[3]]
'''
?
這次是，在最后一層返回時，獲得了一個返回值 [[3]] ，然后回到上一層時，前面又有return 表示需要把本層的返回值，返回到上層的接收處，重復，直到回到最外層，這個從底層傳上來的返回值，一直傳到了最外層，所以才打印出來的，只有最后一層，但是每次一層都獲得了返回值，和例子1 后面兩層沒有返回值是不同的哦！?
# 例3：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? remain = fullpermutation(list[1:])
? ? print(list)
?
?
print(fullpermutation([1, 2, 3]))
'''
輸出結果為：
[2, 3]
[1, 2, 3]
None
'''
?
最后一層碰到return，觸發會的過程，回到調用處，執行阻塞處下面的代碼，打印list，這個list是什么？它就是本層空間 參數的規模（因為代碼寫的是規模不斷變小從[1,2,3]>>>[2,3]>>>[3]）,顯然，從最后一層回到上一層，此時規模是[2,3]，所以打印list 就是[2, 3]；接著繼續回到上一層，即是最外層，規模是[1,2,3]，所以打印[1, 2, 3]，最后的None是因為最外層函數，沒有返回值，所以才打印出None?
# 例4：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? remain = fullpermutation(list[1:])
? ? return list
?
?
print(fullpermutation([1, 2, 3]))
'''
輸出結果為：
[1, 2, 3]
'''
?
依照上面的步驟，觸發回的過程，只要沒有到達最外層，return list 返回本層的規模（參數規模），那么這個返回值就會給本層的接收者 remain 不可能給最外層的接收者，雖然這里沒有打印 remain的值，但是這里的remain和第一個列子中的remain，后面層數是有返回值的哦（下面例子就會體現），本例，返回到最外層時，list的本層規模為 [1,2,3] 最外層接收者接收到，然后打印出來，所以是[1,2,3]?
# 例5：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? remain = fullpermutation(list[1:])
? ? print(remain)
? ? return list
?
?
print(fullpermutation([1, 2, 3]))
'''
輸出結果為：
[[3]]
[2, 3]
[1, 2, 3]
'''
?
看上面的例子，這次我們是打印了 remain，因為返回的過程中，指向阻塞處（調用處）下面的代碼，每次return list 即是 在本層返回 當前的參數規模，所以 remain 是能接收本層的返回值的，所以會打印 [[3]] ，[2, 3] ；最后 [1, 2, 3] 是最外層打印的?
# 例6：
def fullpermutation(list):
? ? if list is None:
? ? ? ? return None
? ? if len(list) == 1:
? ? ? ? return [list]
? ? res = []
? ? pivot = list[0]
? ? remain = fullpermutation(list[1:])
? ? print(remain)
? ? print(list)
? ? return list
?
?
print(fullpermutation([1, 2, 3]))
'''
輸出結果為：
[[3]]
[2, 3]
[2, 3]
[1, 2, 3]
[1, 2, 3]
'''
?
?這個，就是所有的融合；通過上面的代碼我們來總結下return的返回值：最后一層遇到的return 需要執行 回的過程，此時的返回值 值會返回給最后的調用處的接收者；然后執行 阻塞處下面的代碼時，如果又遇到return 這里的返回值，如果沒有到達最外層，都是給本層的接收者！為什么要大費周章的講這個，是因為我們在寫遞歸時，往往不清楚return 要怎么寫，已及它的返回值是什么？接下來就要看下return 如何解決問題的? 請用遞歸完成一個字符串的反轉，輸入字符串“abcd”，完成翻轉成“dcba” 除了遞歸，我們可以直接用字符串的切片來完成，如下，但是這里是要講遞歸的思想，不體現方法優劣！??
s="abcd"
print(s[::-1])
?
想一下遞歸的思路該怎么做？ 思路一：按照上面的例子，不斷的劃分子規模，我們選的是劃分原字符串的規模，都是往后截取的，比如第一次參數s=“abcd” 我們取參數s[1:] ，不斷調用函數，每次傳入參數為：‘bcd’ ‘cd’ ‘d’ ，這樣最后一層返回d 我們能拿到最后一個值，然后最后一個返回值d 加上 當前規模的第一個值，就完成了反轉，具體代碼如下：?
def str_reverse(s):
? ? if len(s) <= 1: # 遞歸出口
? ? ? ? return s
? ? # last = str_reverse(s[1:])
? ? # return last + s[0]
? ? return str_reverse(s[1:]) + s[0] # 每次返回最后一層的值，加上當前規模的第一個值
?
思路二：改變下子規模，我們這次不劃分原字符串，而是從它的索引下手，傳入最后一個元素的索引，不斷去遞歸索引的值，這時，變的是end的值，從 3 到 2 1 0，到0時觸發回的過程，返回當前索引的值，即是 a （不斷向前取值），這時我們再加上當前層的s，因為沒有劃分s所以s每一層都是等于‘abcd’的，我們每次取當前end索引指向的字符串的值，等于從前往后遍歷字符串 ‘abcd’ ，兩部分鏈接起來，就完成了反轉：每次的返回值為 a, ba , cba, dcba,?
def reve(str, end):
? ? if end == 0:
? ? ? ? return "" + str[0]
? ? last = str[end] + reve(str, end - 1)
? ? return last
?
?
s = "abcd"
print(reve(s, len(s) - 1))
?
?兩種做法都用到return，而是還有重要的遞歸思路，下面就來看看遞歸要用什么思路來解? 來試下“反轉鏈表”如何用遞歸做，首先對于一個單鏈表，要對它反轉，我們的思路依舊可以通過不斷向后劃分子規模，找到它的最后一個結點，然后從后往前依次改變每個結點的指向，讓最初的頭結點變成尾結點，讓它最后指向None；那么具體步驟是：用遞歸找到最后一個結點，我們可以通過前一個結點的next區域，不斷遞歸，找到下一個結點，直到當前結點的next是None，說明它就是最后一個結點，這也是我們遞歸的出口，那么依次讓它返回，同時改變指向，就完成了，具體看下面的圖解：??
class ListNode:?
? ? def __init__(self, x):
? ? ? ? self.val = x
? ? ? ? self.next = None
?
?
class Solution:
? ? def ReverseList(self, pHead):
? ? ? ? if pHead is None: # 判斷傳入的頭結點是否為空
? ? ? ? ? ? return None
? ? ? ? if pHead.next is None: # 如果只有一個結點，直接返回結點；同時也是遞歸的出口
? ? ? ? ? ? return pHead
? ? ? ? last_node = self.ReverseList(pHead.next) # last_node永遠只接收到了最后一個結點
? ? ? ? pHead.next.next = pHead # 后一個結點，指向前一個結點
? ? ? ? pHead.next = None # 前一個結點，在不同的層，先指向None，如果到達最外層也會指向None
? ? ? ? return last_node # 最后返回最后一個結點，表示反轉成功
?
到達最后一層，觸發回的過程，返回 last_node 結點給最后第四層，執行阻塞處下面的代碼，因為pHead.next.next 是None，它不用改變也行，直接到 return last_node 把 last_node給第三層用… 第三層獲得 last_node ，執行阻塞處下面的代碼，改變指向，pHead.next.next 是“5結點”，它的指針指向 pHead，即是上一個結點，然后上一個結點指向None；因為這里并不需要用一個temp 來保存前一個指針信息，表面上是斷開鏈接，會丟掉數據，其實不會丟掉，因為他們不再同一層；可以用temp先保存前一個結點的數，這屬于遞歸的寫，在我的文章>>>反轉鏈表多種解法 有提到，這里不細說！? 直到 回到最外層，起初的頭結點，自然會指向None，最后返回 last_node即可 這才是 鏈表反轉 遞歸的詳細過程，果然和我開始理解的不一樣，當初怎么都無法理解，直到用斷點調試，才發現真正的過程，是這樣，大家可以用斷點調試下，看下代碼的具體過程，下面是測試代碼：?
class ListNode:
? ? def __init__(self, x):
? ? ? ? self.val = x
? ? ? ? self.next = None
?
?
class Solution:
? ? def ReverseList(self, pHead):
? ? ? ? if pHead is None:
? ? ? ? ? ? return None
? ? ? ? if pHead.next is None:
? ? ? ? ? ? return pHead
? ? ? ? last_node = self.ReverseList(pHead.next)
? ? ? ? print(last_node.val)
? ? ? ? pHead.next.next = pHead
? ? ? ? pHead.next = None
? ? ? ? return last_node
?
? ? def print_list(self, node):? # 打印測試
? ? ? ? if node is None:
? ? ? ? ? ? return None
? ? ? ? while node:
? ? ? ? ? ? print(node.val, end="")
? ? ? ? ? ? node = node.next
? ? ? ? print()
?
?
if __name__ == '__main__':
? ? n1 = ListNode(1)? # 依次實例5個結點
? ? n2 = ListNode(2)
? ? n3 = ListNode(3)
? ? n4 = ListNode(4)
? ? n5 = ListNode(5)
? ? n1.next = n2? # 依次將結點鏈接起來，形成一個鏈表
? ? n2.next = n3
? ? n3.next = n4
? ? n4.next = n5
? ? n5.next = None
?
? ? obj = Solution()
? ? print(obj.ReverseList(n1).val)
? ? # obj.print_list(n1) # 1 2 3 4 5
? ? # obj.print_list(obj.ReverseList(n1))? # 5 4 3 2 1
?
遞歸思路?
?思想： 1.找到當前這個值與上一個值的關系 2.找到程序的出口 有個明確的結束條件 3.假設當前功能已經完成 每次進入更深一層遞歸時，問題規模相比上次遞歸都應有所減少? 遞歸思路： （1）找重復：看哪一部分是 實現函數的變化；每次進入更深一層遞歸時，問題規模相比上次遞歸都應有所減少 （2）找變化：變化的量應該作為參數 （3）找邊界（出口）：終止條件? 遞歸可以分為： （1）直接量+小規模子問題 （2）多個小規模子問題 （3） “切蛋糕”思維 （4）找遞推公式，等價交換公式??
二分法和遞歸?
# 二分法一定是在排序好的數據里使用
?
lst = [33, 22, 44, 55, 66, 88, 77, 99, 101, 238, 345, 456, 567, 678, 789]
n = 76
lst.sort()
left = 0
right = len(lst) - 1
?
while left <= right:? # 條件是 開頭<=結尾
? ? middle = (left + right) // 2
? ? if lst[middle] > n:? # 每次用對折后，中間的數和 查找對象比較
? ? ? ? right = middle - 1
? ? elif lst[middle] < n:
? ? ? ? left = middle + 1
? ? elif lst[middle] == n:
? ? ? ? print("找到了")
? ? ? ? break
else:
? ? print("這個數不在列表中")
?
# 遞歸函數來做
lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]
?
?
def func(n, left, right):
? ? if left <= right:? # 邊界
? ? ? ? mid = (left + right) // 2
? ? ? ? if n > lst[mid]:
? ? ? ? ? ? left = mid + 1
? ? ? ? ? ? func(n, left, right)? # 遞歸的入口,目的是再確定一次中間的位置
? ? ? ? elif n < lst[mid]:
? ? ? ? ? ? right = mid - 1
? ? ? ? ? ? func(n, left, right)
? ? ? ? elif n == lst[mid]:
? ? ? ? ? ? print("找到了")
? ? ? ? ? ? return? # 遞歸出口
? ? else:
? ? ? ? print("沒有這個數")
? ? ? ? return? # 遞歸的出口
?
?
func(66, 0, len(lst) - 1)
?
# 升級：如果找到了要求的數，請返回它的索引
?
lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]
?
?
def func(n, left, right):
? ? if left <= right:? # 邊界
? ? ? ? mid = (left + right) // 2
? ? ? ? if n > lst[mid]:
? ? ? ? ? ? left = mid + 1
? ? ? ? ? ? return func(n, left, right)? # 每一層都要返回給上一層的調用者
? ? ? ? elif n < lst[mid]:
? ? ? ? ? ? right = mid - 1
? ? ? ? ? ? return func(n, left, right)
? ? ? ? elif n == lst[mid]:
? ? ? ? ? ? print("找到了")
? ? ? ? ? ? return mid? # 多層函數只會將返回值返回給上一層的調用者
? ? else:
? ? ? ? print("沒有這個數")
? ? ? ? return -1
?
?
print(func(66, 0, len(lst) - 1))
?
尾遞歸?
尾遞歸（自己調用自己，且非表達式：把值放到參數中算）
?
?
>>>求斐波那契數列第n位是幾？(尾遞歸做法)
?
def feibo(num, res, temp):
? ? ?#使用尾遞歸法求解斐波那契數量的第num個數字
? ? ?if num == 0:
? ? ? ? ? return res
? ? ?else:
? ? ? ? ? return feibo(num - 1, temp, res + temp)
?
print(feibo(10,0,1))
?
# 直接遞歸? 尾遞歸 與 循環 的對比
?
import time
?
?
def Fib_recursion(num):
? ? '''
? ? 直接使用遞歸法求解斐波那契數量的第num個數字
? ? '''
? ? if num < 2:
? ? ? ? return num
? ? return Fib_recursion(num - 1) + Fib_recursion(num - 2)
?
?
def Fib_tail_recursion(num, res, temp):
? ? '''
? ? 使用尾遞歸法求解斐波那契數量的第num個數字
? ? '''
? ? if num == 0:
? ? ? ? return res
? ? else:
? ? ? ? return Fib_tail_recursion(num - 1, temp, res + temp)
?
?
def Fib_circle(num):
? ? '''
? ? 直接使用循環來求解
? ? '''
? ? a = 0
? ? b = 1
? ? for i in range(1, num):
? ? ? ? c = a + b
? ? ? ? a = b
? ? ? ? b = c
? ? return c
?
?
if __name__ == '__main__':
? ? num_list = [5, 10, 20, 30, 40, 50]
? ? for num in num_list:
? ? ? ? start_time = time.time()
? ? ? ? print(Fib_recursion(num))
? ? ? ? end_time = time.time()
? ? ? ? print(Fib_tail_recursion(num, 0, 1))
? ? ? ? end_time2 = time.time()
? ? ? ? print(Fib_circle(num))
? ? ? ? end_time3 = time.time()
? ? ? ? print('正在求解的斐波那契數字下標為%s' % num)
? ? ? ? print('直接遞歸耗時為 ：', end_time - start_time)
? ? ? ? print('尾遞歸調用耗時為：', end_time2 - end_time)
? ? ? ? print('直接使用循環耗時為：', end_time3 - end_time2)
?
遞歸練習題?
>>>打印f-e的數：
?
def pri(f, e):
? ? if f > e:
? ? ? ? return
? ? else:
? ? ? ? print(f)
? ? ? ? return pri(f + 1, e)
?
?
pri(1, 6)
?
?
>>>求一個列表的和：
def sum_lis(li, f):? # 如果單獨是傳入一個列表，它體現不了變化
? ? """
? ? :param li: 傳入一個列表
? ? :param f: 列表起始位置
? ? :return: 列表和
? ? """
? ? if f == len(li) - 1:? # 表示起始位置也是結束位置，即只有一個元素
? ? ? ? return li[f]
?
? ? return li[f] + sum_lis(li, f + 1)
?
?
print(sum_lis([1, 2, 3, 4, 5], 0))
?
# 多引入一個 變化的參數，可以想到第一個元素加上剩下的元素，規模不斷變小
?
# 需求:求 1+2+3+4........100 的和
num = 1
count = 0
while num <= 100:
? ? count += num
? ? num += 1
print(count)
?
'''
思路：
sum(1) + 2 +3.....100
sum(2) + 3........100
sum(3) + 4........100
...
sum(98)+99+100
sum(99) + 100
sum(100)
?
sum(100) = sum(99) + 100
sum(99) = sum(98) + 99
sum(98) = sum(97) + 98
.....
?
sum(2) = sum(1) + 2
?
sum(1) = 1
'''
# 用遞歸函數解決
def sum(num):
? ? if num == 1:? # 出口
? ? ? ? return 1
? ? return num + sum(num - 1)? # 一直返回sum(num-1)+num，每次遞歸調用，有return才能有返回值
?
?
print(sum(100))
?
>>>需求：打印斐波那契數列
def fibo(num):? # 參數是表示第n個斐波那契數，函數整體表示獲取斐波那契數列中第n個數字的值
? ? if num == 1 or num == 2:? # 第一個和第二個都是1
? ? ? ? return 1? # 返回1，出口
? ? return fibo(num - 1) + fibo(num - 2)? # 規律，后一項加上后兩項，就等于斐波那契數列第n個數字的值
?
?
if __name__ == '__main__':
? ? list_num = []? # 創建一個空列表，開始
? ? for i in range(1, 21):? # 遍歷1-20
? ? ? ? list_num.append(fibo(i))? # 注意這里開始調用函數，獲得一個斐波那契數字，將獲取到的值填充到list_num
? ? print(list_num)
?
?
# 最佳解法：
def fei_bo(n):
? ? if n <= 1:
? ? ? ? return (n, 0)
? ? else:
? ? ? ? (a, b) = fei_bo(n - 1)
? ? ? ? return (a + b, a)
?
?
print(fei_bo(5))
# 這里是線性的解法，不再重復計算前一項已知的數
?
# 求最大公約數
def maxg(m, n):
? ? if n == 0:
? ? ? ? return m
? ? return maxg(n, m % n)
?
?
print(maxg(6, 0))
?
# 最大公約數：
# 如果m%n=0 則n是m的最大公約數；例如4%2=0 則2是最大公約數?
# 如果m%n=K 則 n%k=?0 >>> f(m,n)=f(n,m%n)
?
?
>>>用遞歸實現列表排序：
def ins(li, k):
? ? if k == 0:
? ? ? ? return
? ? # 對前K個元素進行排序
? ? ins(li, k - 1)
? ? # 把位置K的元素插入到前面的部分
? ? x = li[k]
? ? index = k - 1
? ? while x < li[index]:
? ? ? ? li[index + 1] = li[index]
? ? ? ? index -= 1
? ? li[index + 1] = x
? ? print(li)
?
?
ins([1, 4, 3, 2], 3)
?
>>>需求：遞歸實現遍歷目錄
?
import os
?
?
def get_alldirfile(source_path):? # 定義一個函數獲取用戶輸入的路徑名下所有目錄和文件
? ? if not os.path.exists(source_path):? # 判斷用戶輸入的目錄是否存在
? ? ? ? return? # 不存在，直接返回，結束該函數，找到一個出口
? ? list_name = os.listdir(source_path)? # lisdir獲取所有目錄，并全部放到一個列表中
? ? for flie_dirname in list_name:? # 遍歷下所有的文件目錄名
? ? ? ? abs_path = os.path.join(source_path, flie_dirname)? # 拼接成絕對路徑
? ? ? ? # 判斷下一級是否是目錄還是文件，是文件結束，是目錄繼續深入，直到是文件結束
? ? ? ? if os.path.isfile(abs_path):? # 是文件
? ? ? ? ? ? print("file_path:%s" % (abs_path))
? ? ? ? # 也可進行復制操作，open(abs_path,"w",encoding="utf-8")
? ? ? ? if os.path.isdir(abs_path):
? ? ? ? ? ? get_alldirfile(abs_path)? # 遞歸函數
?
?
if __name__ == '__main__':
? ? path = r"F:\日語\快樂50音"
? ? get_alldirfile(path)
?
# 優化
import os
?
?
def file_get(file_path, n):
? ? list_file = os.listdir(file_path)
? ? for file in list_file:
? ? ? ? abs_file = os.path.join(file_path, file)
? ? ? ? if os.path.isdir(abs_file):
? ? ? ? ? ? print("\t" * n, file)
? ? ? ? ? ? file_get(abs_file, n + 1)
? ? ? ? else:
? ? ? ? ? ? print("\t" * n, file)
?
?
file_get("D:\KuGou", 1)
總結
以上是生活随笔為你收集整理的[转载] Python 递归 深入理解递归 Python递归剖析，绝对让你看懂！的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： shell -eom_EOM的完整形式是
- 下一篇： JavaScript | 嵌套if的示例