參考鏈接： 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)