關(guān)于遞歸教學(xué)的探討

1、關(guān)于遞歸教學(xué)的探討摘要：遞歸是一種重要的程序設(shè)計方法，但在教學(xué)過程中一直是個難點。本文以遞歸為中心,從遞歸、為何用遞歸、如何用遞歸以及使用遞歸需要注意四個方面組織全文，從方法論的角度對遞歸程序設(shè)計進行系統(tǒng)的闡述。文中不僅介紹了遞歸程序設(shè)計的一般步驟和方法，還介紹了如何通過降階、分治和回溯等策略進行遞歸程序設(shè)計。：遞歸 分治 回溯 漢諾塔問題N 皇后問題引言遞歸在程序設(shè)計基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)以及算法設(shè)計與分析等課程的教學(xué)中都占用重要地位，是一類重要的程序設(shè)計方法，但遞歸教學(xué)一直是個難點。學(xué)生通常會對為何用遞歸、如何用遞歸以及遞歸程序的執(zhí)行過程存在疑惑。究其原因，一方面是各類通常只將遞歸作為一個概念進行

2、簡單介紹，對遞歸的執(zhí)行過程以及遞歸程序設(shè)計的一般性步驟和方法描述過少；更重要的是缺少對遞歸程序設(shè)計方法系統(tǒng)性的概述。本文旨在解決這一問題，全文以遞歸為中心，從遞歸、為何用遞歸、如何用遞歸以及使用遞歸需要注意四個方面組織全文，從方法論的角度對遞歸程序設(shè)計進行系統(tǒng)的闡述。文中一方面結(jié)合漢諾塔問題和 N 皇后問題等經(jīng)典實例介紹了遞歸程序設(shè)計的一般步驟和方法，還介紹了如何通過降階、分治和回溯等策略進行遞歸程序設(shè)計。1遞歸簡單來說，遞歸就是指函數(shù)或者過程在執(zhí)行過程中直接或間接調(diào)用自身的現(xiàn)象。如表 1中的函數(shù)即存在遞歸，稱此類發(fā)生自身調(diào)用的函數(shù)為遞歸函數(shù)，通過設(shè)計遞歸函數(shù)進行問題求解的算法稱為遞歸算法。2

3、 為何用遞歸很多問題可以用遞歸的形式來描述，此時用遞歸進行程序設(shè)計簡單、方便、易懂。如一個正整數(shù) n 的階乘可如下定義：予 x，最后輸出 x 的值 6，整個程序結(jié)束。由上例可見，遞歸通常是把一個大型復(fù)雜層層轉(zhuǎn)化為一個與原問題本質(zhì)相同但規(guī)模更小的子問題來求解，運用遞歸只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量，用遞歸3 如何用遞歸寫出的程序往往十分簡潔易懂。如上節(jié)所述，進行遞歸程序設(shè)計的關(guān)鍵是借助遞歸關(guān)系的定義和遞歸邊界構(gòu)造遞歸函數(shù)，但有些問題的描述中遞歸關(guān)系和遞歸邊界并沒有顯示給出，稱此類問題為隱式遞歸問題。對于顯示遞歸問題，如前所述，直接根據(jù)遞歸關(guān)系的定義

4、和遞歸邊界構(gòu)造出遞歸函數(shù)即可求解；對于隱式遞歸問題則要通過一定的策略來找出隱藏的遞歸關(guān)系和遞歸邊界，常見策略如降階、分治和回溯。3.1 降階若問題規(guī)模較小時易找到解決方案，則可將此小規(guī)模問題及其解決方案作為遞歸邊界；之后類似數(shù)學(xué)歸納法，假設(shè)規(guī)模為 n-1 時會求解，在此基礎(chǔ)上考慮問題規(guī)模為 n 時的解決方案，如此即系的定義便到一個將大規(guī)模問題歸結(jié)為小規(guī)模問題的遞歸關(guān)系。聯(lián)合遞歸邊界和遞歸關(guān)到求解問題的遞歸函數(shù)，稱此種構(gòu)造遞歸算法的策略為降階。下面以漢諾塔問題為例說明如何通過降階構(gòu)造遞歸函數(shù)。所謂漢諾塔問題是指梵塔內(nèi)有 ABC 三個塔座，其中塔座 A 上插有 n 個由小到大羅列的圓盤?，F(xiàn)要求將這

5、些圓盤從塔座 A 上搬動到塔座 C 上，要求一次只能搬動一個盤子,而且要求大盤不能壓小盤，中間允許借助塔座B 臨時存放盤子。假設(shè)欲構(gòu)造遞歸函數(shù) Hanoi(n,x,y,z)輸出將 n 個盤子從塔座 x 借助塔座 y 搬動到塔座z 上的解決方案。首先找出遞歸邊界。顯然，當(dāng)問題規(guī)模足夠只有一個BAC盤子時，可直接將該盤從 x 搬動到 y 即可，此時可直接輸出解決方案 xz。由此遞歸邊界：if(n=1) prf(“%c%c”,x,z)。接下來找遞歸關(guān)系。當(dāng) n1 時，假設(shè) n-1 個盤子能按規(guī)則要求從一個塔座借助另一個塔座搬動到第三個塔座上，則要將 n 個盤子從塔座x 借助 y 搬動到 z 可分為三

6、步：首先將塔座 x 上前 n-1 個小盤從塔座 x 借助塔座 z 搬動到塔座 y 上，之后將塔座 x 上僅剩的盤子從 x 搬動z 上，最后將塔座 y 上 n-1 個盤子從塔座 y 借助塔座x 搬到塔座 z 上。由此遞歸關(guān)系：Hanoi(n-1,x,z,y);prf(“%c%c”,x,z);Hanoi(n-1,y,x,z);根據(jù)上述遞歸邊界和遞歸關(guān)系顯然求解 Hanoi 塔問題的遞歸函數(shù)如表 3 所示。如執(zhí)行語句 Hanoi(3,A,B,C)將輸出：AC AB CB AC BA BC AC3.2 分治若操作對象可定義若干結(jié)構(gòu)相同但規(guī)模更小的部分組成，則對原對象的操作可遞歸分解到其各組成部分上分別

7、進行，如此遞歸分解直到不可再分時停止，此類求解策略稱為分治。根據(jù)分治策略很容易得到相應(yīng)的遞歸關(guān)系定義和遞歸邊界，從而構(gòu)造出具體的遞歸函數(shù)。如非空的二叉樹可看作為由根結(jié)點、根節(jié)點的樹以及根結(jié)點的右子樹三部分組成，每一部分又都是一顆樹。如右圖所示二叉樹 T 可看作由根節(jié)點 A、結(jié)點 B、C的樹和void hanoi(n, char x, char y, char z)if(n= =1)pr f(“%c%c ”,x,z);elsehanoi(n-1, x, z, y);pr f(“%c%c ”,x,z);hanoi(n-1, y, x, z);表 3 Hanoi 塔問題遞歸函數(shù)圖 1 Hanoi 塔

8、問題結(jié)點 D、E、F的右子樹組成。欲設(shè)計遞歸函數(shù) NodeCount(T)求二叉樹 T 的結(jié)點總數(shù)，顯然 T 的結(jié)點數(shù)是 T 的樹結(jié)點數(shù)與 T 的右子樹結(jié)點數(shù)之和再加 1，這實際就是遞歸關(guān)系的定義；再注意到空樹的結(jié)點樹為 0，依次作遞歸邊界，即的遞歸函數(shù)。到表 4 所示所示的樹結(jié)點計數(shù)ABDCFE3.3 回溯回溯也是一種問題求解策略，通常指讓計算機從某種可能的情況出發(fā)自前進行搜索，碰到符合的情況就輸出或者保存起來，在一條路徑上走到“盡頭”后就回到原來的岔路口選擇一條以前沒有走過的路重新向前進行探測，直到找到解或者走完所有路徑為止?；厮菥唧w編程實現(xiàn)時通常都用遞歸：“向前進行搜索”對應(yīng)遞歸調(diào)用，“

9、盡頭”對應(yīng)遞歸邊界。比如 N 皇后問題。題目是說，一個 N*N 的國際象棋棋盤上主放置N 個皇后，使其不能相互，即任何兩個皇后都不能處在棋盤的同一行、同一列、同一條斜線上，要求輸出所有可能的擺放方案。其實，題目就是要找出所有可能的合法情況，可以考慮用回溯法求解。讓計算機逐行前進，每行擺放一個棋子，若合法則前進到下一行。為此可設(shè)遞歸函數(shù) voidNQueens(arrNN,i);第一個參數(shù)代表棋盤，第二個參數(shù)代表目前標(biāo)號為 0 的行到標(biāo)號為 i-1 的行已經(jīng)各有一個棋子，且符合規(guī)則要求。遞歸函數(shù)第一次被調(diào)用時時形參 i 值應(yīng)為 0,函數(shù)體內(nèi)遞歸調(diào)用語句應(yīng)為 NQueens(arr,i+1)。至此

10、遞歸關(guān)系定義已經(jīng)找到，但還有一個問題，即遞歸何時停止或者說計算機前進過程中如何判斷是否 “走到盡頭”。分析可見共有兩種情況：其一，當(dāng)前行下完一個棋子后出現(xiàn)了情況，如同一列或同一斜線上出現(xiàn)了多個皇后，此時應(yīng)抹掉該行所下棋子，在其右側(cè)重新下一個棋子再重新檢查；其二，當(dāng)前行下完一個棋子后仍然合法，但恰巧當(dāng)前行是最后一行，這實際意味著已經(jīng)得到了一種合法的擺放方案，此時應(yīng)輸出該方案，之后抹掉該行所下棋子，在其右側(cè)下一個棋子重新檢查。由上述遞歸邊界和遞歸關(guān)系定義可構(gòu)造遞歸函數(shù)如下:通過上例可見，回溯法的主要特點是遞歸結(jié)束的條件在搜索的最后一步，關(guān)鍵是找到遞歸邊界條件4 遞歸存在void NQueens(a

11、rrNN,i)for (j = 0; jlchild)+NodeCount(T-rchild)+1; return n;表 4 樹結(jié)點計數(shù)的遞歸函數(shù)使用遞歸進行程序設(shè)計思路清晰、代碼簡潔，但遞歸調(diào)用過程中，每一次發(fā)生調(diào)用系統(tǒng)都要將返回地址、局部變量等信息入棧保存，因此，遞歸程序的運行效率較低，而且遞歸次數(shù)過多還容易造成棧溢出。此外，尤其要避免重復(fù)遞歸調(diào)用的現(xiàn)象發(fā)生。比如求Fibnacci 數(shù)列的第 n通過表 6 所示遞歸函數(shù)實現(xiàn)，假設(shè) n=4 則遞歸執(zhí)行過程中發(fā)生的遞歸調(diào)用如圖 3 所示，可見 n=4 時 f(1)已經(jīng)被重復(fù)調(diào)用了 3 次。在 Core 2CPU T5500、內(nèi)存 1G 的機器

12、上進試，計算 f(40)約需 20.374 秒的時間，其主要原因在于計算 f(40)時 f(1)會被重復(fù)調(diào)用 165580141 次；而計算 f(50)更是需要 40 多分鐘！f(4)f(3)f(2)f(2)f(1)f(1)f(0)f(1)f(0)5 結(jié)束語本文系統(tǒng)講述了遞歸的基本概念、使用遞歸進行程序設(shè)計的好處以及如何設(shè)計遞歸程序，結(jié)合 Hanoi 塔問題、N 皇后問題等經(jīng)典實例介紹了通過降階、分治及回溯構(gòu)造遞歸函數(shù)的一般化方法，并對遞歸使用過程中可能存在進行了說明。總地來說，遞歸作為一種重要的程序設(shè)計方法可使得編碼清晰易懂，但存在運行效率較低用當(dāng)中，建議僅當(dāng)傳統(tǒng)方法不方便求解時使用遞歸。，在實際應(yīng)參考文獻：1234,C 程序設(shè)計,：2005.7,趙.程序設(shè)計基礎(chǔ)(基于 C 語言),：200