第5章 遞歸電子課件

第5章遞歸本章講解遞歸。要求理解遞歸概念，掌握建遞歸模型，靈活應(yīng)用遞歸解決復(fù)雜問題。吃貨辦席，要把大塊肉弄熟，但鍋兒只有那么大，一次性裝不下怎么辦？難不倒吃貨！吃貨把大塊肉分成很多小塊肉，再用小竹籃打包，批量放入鍋里蒸烤，直到所有肉蒸烤完。原來大問題分解為若干個(gè)小問題，所有小問題解決了，大問題也就解決了，這是遞歸思想。提綱5.1遞歸概念和原理

5.2遞歸模型5.3遞歸算法應(yīng)用5.4遞歸學(xué)習(xí)總結(jié)5.1遞歸概念和原理1.定義在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱為遞歸。5.1遞歸概念和原理舉例：小口瓶子裝了大半瓶碎石頭，要將所有石頭倒出來，試了幾次都堵在瓶口了。慢慢傾斜慢慢倒，一顆一顆倒，最終全部倒出來了。在這個(gè)例子中，全部石頭倒出來是大問題，倒一顆石頭是與大問題相似的小問題，所有小問題解決了，大問題也就解決了，這就是一種遞歸思想。5.1遞歸概念和原理遞歸思想的本質(zhì)是將1個(gè)復(fù)雜的大問題，通過層層分解，分解為若干個(gè)簡(jiǎn)單的又與大問題相似的小問題，所有小問題解決了，大問題也就解決了。5.1遞歸概念和原理2.工作棧遞歸算法在系統(tǒng)內(nèi)部的執(zhí)行是通過1個(gè)工作棧來實(shí)現(xiàn)的，工作棧工作原理：執(zhí)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址。每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址進(jìn)棧。每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。5.1遞歸概念和原理遞歸過程實(shí)質(zhì)上分為分解過程和返回過程，如圖5.1所示求5！。5.1遞歸概念和原理【算法5.1】簡(jiǎn)單的遞歸求和。思路:利用遞歸調(diào)用完成求和。代碼見算法5.15.1遞歸概念和原理3.應(yīng)用條件滿足下面3個(gè)條件可以運(yùn)用遞歸算法解決問題。（1）大問題可以轉(zhuǎn)化為若干個(gè)小問題來求解，而這些小問題的求解

方法與大問題相似，只是在數(shù)量規(guī)模上不同。（2）遞歸調(diào)用的次數(shù)必須是有限的。（3）必須有結(jié)束遞歸的條件來終止遞歸。5.1遞歸概念和原理4.應(yīng)用場(chǎng)景遞歸算法的應(yīng)用，往往有下面3種情形可應(yīng)用遞歸算法解決問題。（1）定義是遞歸的。如許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。例如，求n!和Fibonacci（斐波那契）數(shù)列等。（2）數(shù)據(jù)結(jié)構(gòu)是遞歸的。如單鏈表結(jié)點(diǎn)結(jié)構(gòu)，其內(nèi)指針域又是1個(gè)單鏈表結(jié)點(diǎn)。（3）求解問題的方法是遞歸的。如求解漢諾塔問題，多級(jí)目錄查找文件問題，等。5.2遞歸模型

5.2遞歸模型5.2遞歸模型【思考與練習(xí)5.2】下面問題的求解，請(qǐng)寫出遞歸模型。求n！求數(shù)組a[0...n-1]中的最大值。求Fibonacci數(shù)列。單鏈表的遍歷。5.2遞歸模型

5.3遞歸算法應(yīng)用【例5.1】創(chuàng)建并初始化1個(gè)不帶頭結(jié)點(diǎn)的單鏈表，分別對(duì)該單鏈表正向和反向輸出其所有結(jié)點(diǎn)。思路：（1）設(shè)f(p)為正向輸出單鏈表所有結(jié)點(diǎn)（a1...an），是大問題，顯然f(p.next)輸出（a2...an）是小問題，當(dāng)p為null時(shí)不做任何事。5.3遞歸算法應(yīng)用

5.3遞歸算法應(yīng)用思路：（2）設(shè)g(p)為反向輸出單鏈表所有結(jié)點(diǎn)（an...a1），是大問題，顯然f(p.next)輸出（an...a2）是小問題，當(dāng)p為null時(shí)不做任何事。與正向輸出不同的是，先讓p移動(dòng)，再輸出p結(jié)點(diǎn)。5.3遞歸算法應(yīng)用

5.3遞歸算法應(yīng)用【進(jìn)一步思考】正反向遍歷順序表，也可以用遞歸算法實(shí)現(xiàn)嗎，為什么？答：可以。同例5.1算法，大問題可以分解為相似的問題，如a[0...n-1]是大問題，a[1...n-1]/a[0...n-2]是小問題。5.3遞歸算法應(yīng)用

5.3遞歸算法應(yīng)用【進(jìn)一步思考】在分析遞歸和非遞歸算法時(shí)空復(fù)雜度時(shí)，有什么不同的考慮？答：在分析非遞歸算法時(shí)，主要看時(shí)間頻度與問題規(guī)模之間的關(guān)系，算法的主要語句執(zhí)行的次數(shù)來確定之，輔助變量與問題規(guī)模是否相關(guān)；在分析遞歸算法時(shí)，要考慮嵌套調(diào)用次數(shù)以及遞歸棧所需空間，即要計(jì)算時(shí)間和空間的遞推式，如例5.2算法中通過時(shí)間和空間遞推式計(jì)算出遞歸算法的時(shí)間和空間復(fù)雜度。5.3遞歸算法應(yīng)用

5.3遞歸算法應(yīng)用

5.3遞歸算法應(yīng)用【進(jìn)一步思考】若用非遞歸算法產(chǎn)生螺旋矩陣，實(shí)現(xiàn)思路又是什么？答：循環(huán)嵌套，對(duì)二維數(shù)組遍歷賦值，賦值是需根據(jù)當(dāng)前行考慮數(shù)學(xué)計(jì)算。5.4遞歸學(xué)習(xí)總結(jié)遞歸算法總可以轉(zhuǎn)換為用棧結(jié)構(gòu)實(shí)現(xiàn)的算法，這是由遞歸工作原理推出的。遞歸算法使得代碼簡(jiǎn)潔、優(yōu)雅，代價(jià)往往是時(shí)空開銷更大。時(shí)空復(fù)雜度分析，對(duì)于非遞歸算法是定長(zhǎng)的，對(duì)于遞歸算法是變長(zhǎng)的。遞歸算法的時(shí)間復(fù)雜度求解有3種常見的方法：遞推式，master定理，遞歸樹。讀者掌握其中1種如遞推式求解即可。遞歸算法的時(shí)間復(fù)雜度=每1次遞歸的時(shí)間復(fù)雜度*遞歸次數(shù)；遞歸算法的空間復(fù)雜度=每1次遞歸的空間復(fù)雜度*遞歸深度。遞歸算法空間復(fù)雜