文章目錄

• 遞歸
• • 問題描述
  • 基線條件和遞歸條件
  • 棧
  • • 調用棧
    • 遞歸調用棧
  • 小結
• 快速排序
• • 示例1
  • • 問題描述
    • 歐幾里得算法
    • 使用D&C解決問題的兩個步驟：
  • 示例2
• 快速排序
• • 工作原理
  • 代碼
• 小結

遞歸

問題描述

假設你在祖母的閣樓中翻箱倒柜，發(fā)現(xiàn)了一個上鎖的神秘手提箱。祖母告訴你，鑰匙很可能在下面這個盒子里，這個盒子里有盒子，而盒子里的盒子又有盒子。鑰匙就在某個盒子中。為找到鑰匙，你將使用什么算法？
方法一：

創(chuàng)建一個要查找的盒子堆。

從盒子堆取出一個盒子，在里面找。

如果找到的是盒子，就將其加入盒子堆中，以便以后再查找。

如果找到鑰匙，則大功告成！

回到第二步。

方法二：

檢查盒子中的每樣東西。

如果是盒子，就回到第一步。

如果是鑰匙，就大功告成！

第一種方法使用的是while循環(huán)：只要盒子堆不空，就從中取一個盒子，并在其中仔細查找。

def look_for_key(main_box):pile = main_box.make_a_pile_to_look_through()while pile is not empty:box = pile.grab_a_box()for item in box:if item.is_a_box():pile.append(item)elif item.is_a_key():print("found the key!")

第二種方法使用遞歸——函數(shù)調用自己，這種方法的偽代碼如下。

def look_for_key(box):for item in box:if item.is_a_box():look_for_key(item) #遞歸elif item.is_a_key():print("found the key!)

遞歸只是讓解決方案更清晰，并沒有性能上的優(yōu)勢。實際上，在有些情況下，使用循環(huán)的性能更好。

基線條件和遞歸條件

由于遞歸函數(shù)調用自己，因此編寫這樣的函數(shù)時很容易出錯，進而導致無限循環(huán)。例如，下面這樣的倒計時函數(shù)。

def countdown(i):print(i)countdown(i-1) print(countdown(3))

運行上述代碼，將發(fā)現(xiàn)一個問題：這個函數(shù)運行起來沒完沒了！（要讓腳本停止運行，可按Ctrl+C。）

編寫遞歸函數(shù)時，必須告訴它何時停止遞歸。正因為如此，每個遞歸函數(shù)都有兩部分：基線條件（base case）和遞歸條件（recursive case）。遞歸條件指的是函數(shù)調用自己，而基線條件則指的是函數(shù)不再調用自己，從而避免形成無限循環(huán)。

def countdown(i)print(i)if i <= 0: #基線條件returnelse: #遞歸條件countdown(i - 1)

棧

調用棧(call stack)只有兩種操作：壓入（插入）和彈出（刪除并讀取）。

調用棧

def greet(name):print("hello, " + name + "!")greet2(name)print("getting ready to say bye...")bye() def greet2(name):print("how are you, " + name + "?") def bye():print("ok bye!") greet("maggie")

假設你調用greet(“maggie”)，計算機將首先為該函數(shù)調用分配一塊內存。

我們來使用這些內存。變量name被設置為maggie，這需要存儲到內存中。

每當你調用函數(shù)時，計算機都像這樣將函數(shù)調用涉及的所有變量的值存儲到內存中。接下來，你打印hello, maggie!，再調用greet2(“maggie”)。同樣，計算機也為這個函數(shù)調用分配一塊內存。

計算機使用一個棧來表示這些內存塊，其中第二個內存塊位于第一個內存塊上面。你打印how are you, maggie?，然后從函數(shù)調用返回。此時，棧頂?shù)膬却鎵K被彈出。

現(xiàn)在，棧頂?shù)膬却鎵K是函數(shù)greet的，這意味著你返回到了函數(shù)greet。

這是本節(jié)的一個重要概念：調用另一個函數(shù)時，當前函數(shù)暫停并處于未完成狀態(tài)。該函數(shù)的所有變量的值都還在內存中。執(zhí)行完函數(shù)greet2后，你回到函數(shù)greet，并從離開的地方開始接著往下執(zhí)行：首先打印getting ready to say bye…，再調用函數(shù)bye。

在棧頂添加了函數(shù)bye的內存塊。然后，你打印ok bye!，并從這個函數(shù)返回。

現(xiàn)在你又回到了函數(shù)greet。由于沒有別的事情要做，你就從函數(shù)greet返回。這個棧用于存儲多個函數(shù)的變量，被稱為調用棧。

遞歸調用棧

遞歸函數(shù)也使用調用棧！如計算階乘的遞歸函數(shù)factorial：

def fact(x):if x == 1:return 1else:return x * fact(x - 1) print(fact(5))

注意，每個fact調用都有自己的x變量。在一個函數(shù)調用中不能訪問另一個的x變量。

棧在遞歸中扮演著重要角色。在本章開頭的示例中，有兩種尋找鑰匙的方法。對于第一種方法，你創(chuàng)建一個待查找的盒子堆，因此你始終知道還有哪些盒子需要查找。

但使用遞歸方法時，沒有盒子堆。既然沒有盒子堆，那算法怎么知道還有哪些盒子需要查找呢？

原來“盒子堆”存儲在了棧中！這個棧包含未完成的函數(shù)調用，每個函數(shù)調用都包含還未檢查完的盒子。使用棧很方便，因為你無需自己跟蹤盒子堆——棧替你這樣做了。

使用棧雖然很方便，但是也要付出代價：存儲詳盡的信息可能占用大量的內存。每個函數(shù)調用都要占用一定的內存，如果棧很高，就意味著計算機存儲了大量函數(shù)調用的信息。在這種情況下，你有兩種選擇。

• 重新編寫代碼，轉而使用循環(huán)。
• 使用尾遞歸。這是一個高級遞歸主題，不在本書的討論范圍內。另外，并非所有的語言都支持尾遞歸。

小結

• 遞歸指的是調用自己的函數(shù)。
• 每個遞歸函數(shù)都有兩個條件：基線條件和遞歸條件。
• 棧有兩種操作：壓入和彈出。
• 所有函數(shù)調用都進入調用棧。
• 調用棧可能很長，這將占用大量的內存

快速排序

分而治之（divide and conquer，D&C）——一種著名的遞歸式問題解決方法。

只能解決一種問題的算法畢竟用處有限，而D&C提供了解決問題的思路，是另一個可供你使用的工具。面對新問題時，你不再束手無策，而是自問：“使用分而治之能解決嗎？”

示例1

問題描述

講一塊長方形的土地，均勻地分成方塊，且分出的方塊要盡可能大。即找出長和寬的最大公約數(shù)

歐幾里得算法

用于查找（A，B）最大公約數(shù)（GCD）的歐幾里得算法如下：

如果A = 0，則GCD（A，B）= B，因為GCD（0，B）= B，我們可以停下來。

如果B = 0，則GCD（A，B）= A，因為GCD（A，0）= A，我們可以停下來。

用余數(shù)形式寫A（A =B?Q+ R），其中Q是除數(shù)，R是余數(shù)。

因為GCD（A，B）= GCD（B，R），所以使用歐幾里得算法找到GCD（B，R）

使用D&C解決問題的兩個步驟：

找出基線條件，這種條件必須盡可能簡單。

不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件。

D&C并非可用于解決問題的算法，而是一種解決問題的思路。

示例2

求數(shù)字數(shù)組之和：

循環(huán)方法

def sum(arr): total = 0 for x in arr: total += x return total print(sum([1, 2, 3, 4]))

遞歸函數(shù)

def sum(xlist):if len(xlist) == 0: #找出基準條件return 0else:return xlist.pop(len(xlist) - 1) + sum(xlist)#縮小問題規(guī)模，每次遞歸調用都必須離空數(shù)組更進一步 print(sum([1, 2, 3, 4, 5]))

編寫涉及數(shù)組的遞歸函數(shù)時，基線條件通常是數(shù)組為空或只包含一個元素。陷入困境時，請檢查基線條件是不是這樣的。

相比較用循環(huán)解決問題，函數(shù)式編程語言沒有循環(huán)，只能使用遞歸來編寫。

快速排序

工作原理

從數(shù)組中隨機選擇一個元素，這個元素被稱為基準值（pivot）。

找出比基準值小的元素以及比基準值大的元素，這被稱為分區(qū)（partitioning）。

對這兩個子數(shù)組進行快速排序，再合并結果，就能得到一個有序數(shù)組。

代碼

def quicksort(array): if len(array) < 2:return array #基線條件：為空或只包含一個元素的數(shù)組是“有序”的else:pivot = array[0]less = [i for i in array[1:] if i < pivot]greater = [i for i in array[1:] if i > pivot]return quicksort(less) + [pivot] + quicksort(greater) print(quicksort([10, 5, 2, 3]))

快速排序的時間復雜度為$O(n?logn)$，這里同樣也省去了系數(shù)，而且是平均運行時間。

快速排序是最快的排序算法之一，也是D&C典范。

小結

• D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數(shù)組或只包含一個元素的數(shù)組。
• 實現(xiàn)快速排序時，請隨機地選擇用作基準值的元素。快速排序的平均運行時間為$O(n?logn)$。
• 大O表示法中的常量有時候事關重大，這就是快速排序比合并排序快的原因所在。
• 比較簡單查找和二分查找時，常量幾乎無關緊要，因為列表很長時$O(logn)$比O(n)快得多。

總結

以上是生活随笔為你收集整理的递归和快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。