<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                ## 10.2 遞歸 我們已經知道,循環是必不可少的基本流程控制結構之一,在編程中時時會用到循環語 句。但出乎意外的是,一個編程語言實際上可以不提供循環語句①!因為有另一種語言構造 可以替代循環,這就是遞歸。 讀者也許聽說過“循環定義”,即在定義概念 A 的時候直接或間接地用到了 A 自身。例 如將“邏輯學”定義成“研究邏輯的科學”,這實際上是同語反復,并未揭示任何新的內涵; 又如將“美麗”定義成“漂亮”,再將“漂亮”定義成“美麗”,這種循環定義實際上也是同 語反復。循環定義是一種常見的邏輯錯誤,應盡量避免使用,但在數學和程序設計中,我們 經常在一個函數的定義中直接或間接地用到該函數自身,這種函數稱為遞歸(recursive②) 函數。通過下面的討論我們會看到,這種遞歸定義不同于循環定義,它能夠明確地定義出函 數的意義。 遞歸是一種強大的算法設計思想和方法,利用遞歸可以輕松解決很多難題。下面我們通 過例子來介紹這種方法。 階乘 數學中的階乘運算通常用下式定義: ``` n! = n x (n - 1) x (n - 2) x ... x 2 x 1 ``` 注意,當 n 為 0 時,其階乘被定義為 1。 如果要編程計算 n 的階乘,可以采用以前介紹過的累積算法模式來實現,累積算法的關 鍵部分是一個循環語句。下面是此方法的實現代碼及執行實例: >>> def fac(n): if n == 0: return 1 else: f = 1 for i in range(1,n+1): f = i * f return f ``` > ① 有一類函數式編程語言(如 Scheme)就不提供循環語句構造。 > ② 英文 recur 的原意為再次發生、重新出現等。被定義的術語又出現在定義之中,就是遞歸。 ``` >>> fac(4) 24 >>> fac(40) 815915283247897734345611269596115894272000000000L ``` 下面我們用另一種方式來觀察階乘的定義。在階乘定義式中,等號右邊的第一個 n 之后 的部分是什么?稍加思考即可看出就是(n-1)的階乘,即階乘定義式可寫成: ``` n! = n x (n - 1)! ``` 這個式子的含義是:n 的階乘定義為 n 乘(n-1)的階乘。我們看到,“階乘”的定義中用到了 “階乘”本身,這就是遞歸定義。 現代編程語言都支持遞歸函數,Python 也不例外。讀者也許會將上面的遞歸定義式直 接翻譯成如下 Python 函數: ``` def fac(n): return n * fac(n-1) ``` 但這個定義是錯誤的。如果執行這個函數,將會形成如下調用鏈條: ``` fac(n) => fac(n-1) => ... => fac(1) => fac(0) => fac(-1) => fac(-2) => ... ``` 顯然,遞歸將無窮無盡地延續下去①。 有效遞歸定義的關鍵是具有終止條件,使得到達某一點后不再遞歸,否則會導致像無窮循環一樣的后果。對階乘來說,當 n=0 時,n!的值定義為 1,此時無需遞歸。在上面的 fac 函數中添加這個終止條件,即可得正確的遞歸版階乘函數: ``` >>> def fac(n): if n == 0: return 1 else: return n * fac(n-1) >>> fac(4) 24 >>> fac(40) 815915283247897734345611269596115894272000000000L ``` 為了理解遞歸函數的執行過程,需要回顧第 4 章中介紹的函數調用與返回的知識。圖10.1 展示了 fac(2)的計算過程。 ![](https://box.kancloud.cn/2016-02-22_56cafce714438.png) 圖 10.1 fac(2)的計算過程 > ① 事實上編程語言中的遞歸層數是有限制的,當突破限制時遞歸過程會終止。 計算 fac(n)時,由于每次遞歸都導致計算更小的數的階乘,因此這個遞歸過程遲早會到 達計算 fac(0)的情形。而根據 fac()的定義,fac(0)直接返回 1,無需遞歸計算。我們稱這種情 形為遞歸定義的奠基情形。對于奠基情形,遞歸函數能夠直接計算結果。 要說明的是,上面的階乘函數定義其實仍然有 bug:當 n 的初始值小于 1 時,調用 fac(n) 會導致無窮遞歸!解決這個問題很容易,只需在程序開始處檢查 n 是否為負數即可,并且僅 當 n 為非負自然數時才能計算階乘。編寫遞歸程序時很容易在終止條件上面犯錯誤,作為好 的編程習慣,我們應當圍繞遞歸奠基情形測試各種情形。 還要說明一點,每次遞歸調用 fac()都相當于調用一個新的函數,系統將為該函數的局 部變量和參數分配新的空間,與其他 fac()調用的局部變量和參數完全沒有關系。初學者在 這一點上也會經常犯錯誤,以為各遞歸調用中使用的變量是全局共享的。在圖 10.1 中有三 次對 fac(n)的調用,這三次調用應當視為獨立的三個函數,其中用到的參數 n 應當視為三個 相互獨立的局部變量。 列表處理 遞歸對于處理列表是非常有用的,因為列表本身就是“遞歸結構”——任一列表都可看 作是由第一個數據成員與剩余數據列表組成的,即:[a1,a2,...,an]可視為由 a1 和[a2,...,an]組成。 編程處理這個列表時,只需要單獨考慮如何處理 a1,而對[a2,...,an]的處理可以通過遞 歸調用來解決。顯然,每次遞歸都導致處理一個更短的列表,如此遞歸下去終將到達空列表 情形,這正可作為奠基情形。在 Python 中通過索引很容易取得列表 list 的第一個數據和剩 余數據列表,它們分別是 list[0]和 list[1:]。 作為例子,下面我們寫一個遞歸函數來逆向顯示列表的數據,即將[a1,a2,...,an]顯 示為 ``` an,...,a2,a1 ``` 根據列表的“遞歸結構”性質,不難形成這樣的遞歸思考:為了逆向顯示 list,只需先 逆向顯示 list[1:],然后顯示 list[0];當剩余數據列表為空時停止遞歸。這個遞歸思考可以直 接翻譯成如下 Python 代碼: ``` >>> def revList(list): if list != []: revList(list[1:]) print list[0], else: return >>> revList([1,2,3,4,5]) 5 4 3 2 1 ``` 對于簡單列表的處理任務,用 for 循環語句也很容易實現;但當列表很復雜(例如列表 中的元素本身可能是列表),用循環語句就很難編程,而用遞歸則可以很容易地解決問題。 作為練習,讀者不妨思考一下如何逆向顯示如下形狀的列表: ``` [1,[2,3],4,[5,6,[7,8],9]] ``` 二分搜索 10.1 節中介紹了線性搜索算法,讀者已經知道線性搜索的優點是適合無序的數據列表,缺點是不適合大量數據。當列表中的數據有序時,存在更好的搜索策略,這個策略的基本思 想可以通過一個猜數游戲展現出來。 假設某甲心中想好了一個 100 以內的自然數,讓某乙來猜這個數。某乙每猜一次,某甲 都會告訴他猜對了、猜大了或猜小了三種情形之一。某乙該采用什么策略來玩這個游戲呢? 某乙可以每次都隨機猜一個數,也可以系統化地按 1、2、3、……的順序猜(此即線性搜索), 但這兩種策略平均需要猜很多次才能猜中。最好的策略是先猜 1~100 的中間數 50,如果猜 中自不必說,如果猜大了則接下去猜 1~49 的中間數 25,如果猜小了則接下去猜 51~100 的中間數 75。依此類推,每次都猜可能值范圍的中間值,直至猜中。這個策略就是我們要 介紹的二分搜索(binary search)算法。 下面我們利用二分搜索來解決在一個有序數據列表 list 中查找指定數據 x 的問題。先看 如何利用循環來實現二分搜索。算法的核心是一個循環,每一次循環都檢查當前搜索范圍的 中間數據是否等于 x;不等的話,根據大小信息重新設定搜索范圍;如果找到了 x,或者沒 有剩余數據了,則循環終止。為了便于設定搜索范圍,可以用兩個變量 low 和 high 分別記 錄搜索范圍的兩端,每次循環后根據比較結果調整這兩個變量即可重新設定搜索范圍。代碼 如下: ``` def binary(list,x): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) / 2 if list[mid] == x: return mid elif list[mid] > x: high = mid - 1 else: low = mid + 1 return -1 ``` 再看二分搜索的遞歸實現。二分搜索算法可以這樣表達:檢查當前搜索范圍的中間數據, 如果該數據就是目標數據,則算法結束;如果不是,則選擇某一半范圍重新進行二分搜索。 這段話可以翻譯成如下偽代碼: ``` 二分搜索算法:在范圍 list[low]到 list[high]之間查找 x 取當前范圍的中間數據 m; 如果 m 等于 x 或者 m 不存在則算法結束; 如果 x &lt; m 則在范圍 list[low]到 list[mid-1]之間查找 x, 否則在范圍 list[mid+1]到 list[high]之間查找 x。 ``` 這個算法中有三處(見劃線部分)涉及幾乎相同的操作,這正是二分搜索的遞歸性質的 體現。奠基情形是找到了目標值或者檢查完所有數據都未找到目標值,這時將不再遞歸。由 于每次遞歸調用都將搜索空間減小了一半,因此遲早會到達奠基情形。下面給出遞歸版本二 分搜索的 Python 代碼實現。注意與循環版本不同的是,每次遞歸都需要指明搜索范圍,因 此我們將搜索范圍的兩個端點 low 和 high 也作為函數參數。 ``` >>> def recBinSearch(list,x,low,high): if low > high: return -1 mid = (low + high) / 2 m = list[mid] if m == x: return mid elif x < m: return recBinSearch(list,x,low,mid-1) else: return recBinSearch(list,x,mid+1,high) >>> recBinSearch([1,3,5,7,9],5,0,4) 2 >>> recBinSearch([1,3,5,7,9],6,0,4) -1 ``` 階乘和二分搜索這兩個例子說明,許多問題既可用循環(或稱迭代)來實現,也可用遞 歸來實現。很多情況下,兩種方法在設計上都很容易;但對有些問題,迭代算法很難設計, 而遞歸算法則非常容易得到,例如下面的 Hanoi 塔問題。 Hanoi 塔問題 Hanoi 塔問題是體現遞歸方法強大能力的經典例子,該問題涉及如下故事:在某個寺廟 里有三根柱子(不妨稱為 A、B、C 柱),A 柱上有 n 個同心圓盤,圓盤尺寸各不相同,并且 小盤疊在大盤之上,B 柱和 C 柱為空(參見圖 10.2)。寺廟的僧侶們有一項任務:將 n 個圓 盤從 A 柱移到 C 柱,移動過程中可以利用 B 柱作為臨時存放柱。具體的移動圓盤的規則是: + 圓盤只能放在柱子上; + 每次只能移動位于任一柱子頂部的圓盤; + 大圓盤永遠不能置于小圓盤之上。 ![](https://box.kancloud.cn/2016-02-22_56cafce72a4e4.png) 圖 10.2 Hanoi 塔問題 下面我們來設計解決此問題的算法,該算法能夠給出搬運步驟。例如對于 n = 3 的情形,算法將顯示如下移動過程(其中 A -&gt; C 表示將 A 柱頂部圓盤移至 C 柱頂部,余類推): ``` A -> C A -> B C -> B A -> C B -> A B -> C A -> C ``` Hanoi 塔問題看上去有點難度,但如果采用遞歸方法,算法是非常簡單的。稍加思考即 可明白,為了將 A 柱上的所有圓盤移到 C 柱,必然需要有一步將底部的最大圓盤從 A 柱移 到 C 柱,而為此又必須先將最大圓盤上面的 n - 1 個圓盤從 A 柱移到 B 柱,從而形成最大 圓盤之上沒有其他圓盤、同時 C 柱上也沒有圓盤的局面(參見圖 10.3)。 ![](https://box.kancloud.cn/2016-02-22_56cafce73b31d.png) 圖 10.3 為移動最大圓盤必須形成的格局 至此,可以將最大圓盤從 A 柱移到 C 柱,顯然接下去再也不需要移動這個圓盤了,因此可視為不存在。這時形成的局面(圖 10.4)與初始局面非常相似,即:B 柱上有 n - 1 個 圓盤,A 柱和 C 柱為空(無視最大圓盤)。于是任務變成了:將 n - 1 個圓盤從 B 柱移動到 C 柱,移動過程中可以利用 A 柱作為臨時存放柱。將這里的黑體部分文字與前面的初始問 題文字相比較,即可看出 Hanoi 塔問題的遞歸性質:一旦最大圓盤到達目的地,剩下來的問 題恰好又是初始 Hanoi 塔問題,只不過問題規模變成了 n - 1,并且 A 柱和 B 柱的角色相互 交換。 ![](https://box.kancloud.cn/2016-02-22_56cafce748452.png) 圖 10.4 最大圓盤就位之后的格局 根據以上分析,容易得到解決 Hanoi 塔問題的算法。下面是算法的偽代碼: ``` 算法:將 n 個圓盤從 A 柱移到 C 柱,以 B 柱作為臨時存放柱。 將 n - 1 個圓盤從 A 柱移到 B 柱,以 C 柱作為臨時存放柱; 將最大圓盤從 A 柱移到 C 柱; 將 n - 1 個圓盤從 B 柱移到 C 柱,以 A 柱作為臨時存放柱。 ``` 從算法中可見,通過遞歸,我們將規模為 n 的問題轉化成了兩個規模為 n – 1 的問題。 如此遞歸下去,最終將轉化成規模為 1 的問題。而 n = 1 的 Hanoi 塔問題是平凡的,直接移 動一步即可,不再需要遞歸,這就是奠基情形。有了奠基情形,每次遞歸又導致問題規模變 小,可見上述遞歸算法能正確終止。下面我們給出對上述算法的 Python 實現,并對 n = 3 的 情形進行驗證。代碼中 hanoi 函數的參數分別表示圓盤個數和三根柱子(源、目的地、臨時 存放)。 ``` >>> def hanoi(n,source,dest,temp): if n == 1: print source,"->",dest else: hanoi(n-1,source,temp,dest) hanoi(1,source,dest,temp) hanoi(n-1,temp,dest,source) >>> hanoi(3,"A","C","B") A -> C A -> B C -> B A -> C B -> A B -> C A -> C ``` 至此,一個看上去挺難的問題通過遞歸就輕松地解決了。讀者有興趣的話不妨試試如何 利用循環(迭代)來解決 Hanoi 塔問題。 最后對遞歸方法做個小結。 遞歸是非常重要的算法設計方法,在解決很多具有遞歸性質的問題、結構的時候,設計 遞歸算法往往是直接而簡單的。遞歸定義必須滿足以下條件才是良定義的: + 有一個或多個無需遞歸的奠基情形; + 遞歸總是針對規模更小的問題。 有了這兩個條件,遞歸鏈最終將到達奠基情形,從而使遞歸過程終止。 雖然遞歸算法容易設計、實現,也容易理解,但遞歸是有代價的。由于遞歸涉及大量的 函數調用,因此需要耗費較多的內存和較長的執行時間,即遞歸算法的效率較差。而迭代算 法不涉及函數調用,故速度更快,更節省內存。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看