遞歸思想及其算法設(shè)計(jì)的探討

楊 嬌

（陸軍步兵學(xué)院計(jì)算機(jī)教研室，南昌 330103）

今天，在以培養(yǎng)學(xué)員計(jì)算思維為導(dǎo)向的新一輪計(jì)算機(jī)教學(xué)改革的浪潮下，結(jié)合自身多年軟件項(xiàng)目經(jīng)驗(yàn)，以提升學(xué)員計(jì)算思維能力為出發(fā)點(diǎn)，把遞歸的逆向思維及其魅力分享給大家，希望和同行共同探討。

1 遞歸的重要性

《程序設(shè)計(jì)基礎(chǔ)》、《數(shù)據(jù)結(jié)構(gòu)》、《算法設(shè)計(jì)與分析》是計(jì)算機(jī)軟件的專業(yè)基礎(chǔ)課程，呈現(xiàn)出從知識(shí)到能力再到思維的螺旋式上升的遞進(jìn)關(guān)系，遞歸一直伴隨其中，如《程序設(shè)計(jì)基礎(chǔ)》中的遞歸語(yǔ)法結(jié)構(gòu)和執(zhí)行流程、《數(shù)據(jù)結(jié)構(gòu)》中的多分支遞歸、《算法設(shè)計(jì)與分析》中的遞歸性能分析與遞歸轉(zhuǎn)換等。而且，在常用算法中，分治法、回溯法、動(dòng)態(tài)規(guī)劃法在很大程度上也依賴遞歸來(lái)實(shí)現(xiàn)。從實(shí)際情況看，也只有長(zhǎng)期的不斷積累才能深刻領(lǐng)悟遞歸的精髓，有時(shí)遇到項(xiàng)目中一個(gè)小問(wèn)題，就因?yàn)闆](méi)有捋順遞歸關(guān)系而花了一晚上還沒(méi)搞清楚。足可見(jiàn)遞歸的重要性。

2 遞歸知識(shí)的構(gòu)建

掌握構(gòu)建關(guān)于遞歸的知識(shí)結(jié)構(gòu)的概念，訓(xùn)練學(xué)員逆向思維、計(jì)算思維，培養(yǎng)用遞歸思想分析和解決較復(fù)雜問(wèn)題能力。

3 講授過(guò)程中的指導(dǎo)思想

以提出問(wèn)題為切入點(diǎn)，激發(fā)學(xué)員的學(xué)習(xí)興趣。以解決問(wèn)題為中心點(diǎn)，提高學(xué)員的認(rèn)知水平。以滲透思想為關(guān)鍵點(diǎn)，培養(yǎng)學(xué)員的創(chuàng)新意識(shí)。

4 遞歸知識(shí)點(diǎn)教學(xué)內(nèi)容與方法設(shè)計(jì)

在內(nèi)容安排上以遞歸為核心，分二個(gè)部分展開(kāi)：第一部分為遞歸印象，引領(lǐng)學(xué)員快速回憶起遞歸的基本思想；第二部分為遞歸之美，是遞歸的重點(diǎn)內(nèi)容，通過(guò)分析和學(xué)員共同分享遞歸思想的靈魂。在講授方法安排上，一是通過(guò)視覺(jué)遞歸圖片、爬樓梯、畫(huà)樹(shù)等趣味實(shí)例牽引教學(xué)，激發(fā)學(xué)員的學(xué)習(xí)熱情；二是由易及難，合理設(shè)置問(wèn)題陷阱，構(gòu)建問(wèn)題鏈，引領(lǐng)學(xué)員向著問(wèn)題縱深思考和探究；三是多種方法手段相結(jié)合，理論與實(shí)踐演示相結(jié)合，消除學(xué)員畏難情緒，激勵(lì)學(xué)員不斷探索未知。

4.1 通過(guò)視覺(jué)遞歸圖片、故事、數(shù)學(xué)問(wèn)題將學(xué)員快速帶入到遞歸

遞歸現(xiàn)象大家并不陌生，如圖1所示，展示的內(nèi)容是畫(huà)家在畫(huà)一幅畫(huà)，畫(huà)什么畫(huà)？畫(huà)的又是“一個(gè)畫(huà)家在畫(huà)一幅畫(huà)”，如此一直下去，下面的圖片也是如此，大家所熟知的“老和尚給小和尚講故事”的故事也是如此，這是我們對(duì)于遞歸的印象。遞歸不僅存在照片中、故事中，在大家熟知的數(shù)學(xué)知識(shí)中也是比比皆是，如n!，F(xiàn)ibonacci數(shù)列，都揭示了遞歸的本質(zhì)：在一個(gè)事物的組成或定義中又包含了它自己（即遞歸的定義）。在計(jì)算機(jī)領(lǐng)域也是如此，在學(xué)習(xí)《函數(shù)定義與調(diào)用》時(shí)就明確了函數(shù)可以調(diào)用自身，這就是函數(shù)的遞歸，分為直接遞歸和間接遞歸。直接遞歸是指函數(shù)調(diào)用自身。間接遞歸是指在調(diào)用f1函數(shù)時(shí)要調(diào)用f2函數(shù)，在調(diào)用f2函數(shù)時(shí)又要調(diào)用f1函數(shù)。

圖1

在面對(duì)n！這樣并不復(fù)雜的數(shù)值類遞歸問(wèn)題時(shí)，同學(xué)們大都能非常快速的寫(xiě)出正確的遞歸代碼。當(dāng)N=4時(shí)，該函數(shù)在執(zhí)行時(shí)的調(diào)用次序?yàn)?、3、2、1、0，按反序返回。但是需要同學(xué)們真正掌握的不是代碼本身。而是代碼所蘊(yùn)含的遞歸的基本結(jié)構(gòu)：遞歸出口和遞歸體。

4.2 現(xiàn)實(shí)生活問(wèn)題如何轉(zhuǎn)化為數(shù)學(xué)問(wèn)題的遞歸

在以上基礎(chǔ)上，我們不妨看看如何借助計(jì)算機(jī)解決實(shí)際問(wèn)題。如圖所示：小孩上樓回家，一次爬1階或2階，請(qǐng)問(wèn)他有多少種上樓梯的方法？可以一步步上，也可以1步、2步、2步上，還可以有其他的方法，可以窮舉嗎？如果是n級(jí)的臺(tái)階，顯然窮舉不是解決問(wèn)題的辦法，我們得尋找其他方法。

n-1級(jí)臺(tái)階與n級(jí)臺(tái)階的問(wèn)題具有相似性，只是規(guī)模相對(duì)較小。假設(shè)上5級(jí)臺(tái)階有f（5）種方法，不妨看看小孩最后一步的情況，可以是1步上來(lái)，前面4級(jí)臺(tái)階的上法為f（4），也可以是2步上來(lái)，前面3級(jí)臺(tái)階的上法為f（3），這樣總的上法為：f（5）=f（4）+f（3）。有了這樣的結(jié)論，我們不難分析出 f（n）的情況為：f（n）=f（n-1）+f（n-2）。很容易分析 n=0，1是的情況為 ：f（0）=1，f（1）=1。這是一個(gè)Fibonacci數(shù)列。這個(gè)數(shù)列的實(shí)現(xiàn)代碼和n！結(jié)構(gòu)一樣，幾乎沒(méi)有區(qū)別，我們暫且先放下。

圖2

圖3

4.3 用遞歸算法來(lái)實(shí)現(xiàn)現(xiàn)實(shí)中的遞歸之美

前面面對(duì)的都是能用數(shù)列公式描述的遞歸問(wèn)題。實(shí)際生活和軟件項(xiàng)目中還存在著另外一大類的非數(shù)值型的遞歸現(xiàn)象，如我們開(kāi)始時(shí)看到的畫(huà)家圖片。接下來(lái)我們就一起來(lái)學(xué)習(xí)如何用遞歸算法來(lái)實(shí)現(xiàn)現(xiàn)實(shí)中的遞歸之美。圖2是網(wǎng)友在微博上發(fā)的一棵樹(shù)的照片，圖3是計(jì)算機(jī)畫(huà)出來(lái)的一棵二叉樹(shù)，計(jì)算機(jī)是如何做到的？仔細(xì)觀察這棵樹(shù)，看看能發(fā)現(xiàn)些什么？發(fā)現(xiàn)這棵樹(shù)由樹(shù)干、左子樹(shù)、右子樹(shù)三部分構(gòu)成。左右子樹(shù)仍然是一棵樹(shù)，并且子樹(shù)與樹(shù)的結(jié)構(gòu)是完全一致的，只不過(guò)它的規(guī)模比原來(lái)的樹(shù)小。假設(shè)樹(shù)的深度是n，子樹(shù)的深度則為n-1。這樣我們就把一個(gè)規(guī)模為n的畫(huà)樹(shù)的問(wèn)題，分解為了兩個(gè)規(guī)模為n-1的子問(wèn)題和一個(gè)畫(huà)樹(shù)干的情況。

那么畫(huà)一棵樹(shù)需要哪些參數(shù)呢？樹(shù)的深度、樹(shù)干的起點(diǎn)坐標(biāo)、樹(shù)干的高度、樹(shù)干的角度、樹(shù)干的粗細(xì)等，因此在畫(huà)子樹(shù)之前還要做一些計(jì)算子樹(shù)形態(tài)的工作，于是我們可以寫(xiě)出如下的代碼。

4.4 陷阱設(shè)置無(wú)遞歸出口

我們不妨在計(jì)算機(jī)上運(yùn)行一下代碼，試試看畫(huà)出來(lái)的效果。很奇怪，畫(huà)不下去，程序還崩潰了。程序哪里出了問(wèn)題了呢？原來(lái)是一直在畫(huà)子樹(shù)，沒(méi)有停下來(lái)的時(shí)候?！袄虾蜕薪o小和尚講故事”可以一直講下去，但計(jì)算機(jī)程序不能無(wú)限制進(jìn)行下去，我們的程序只有遞歸體，沒(méi)有了遞歸出口，所以才會(huì)這樣。當(dāng)畫(huà)到子樹(shù)的層數(shù)為0的時(shí)候，遞歸就可以終止了。加入遞歸出口、調(diào)整畫(huà)子樹(shù)的順序、加入樹(shù)干顏色和樹(shù)葉的顏色，得到如下代碼。

以上得到的是一棵非常規(guī)整的二叉樹(shù)，怎么樣可以更接近真實(shí)呢？可以使得子樹(shù)的角度隨機(jī)、高度隨機(jī)、樹(shù)干粗細(xì)隨機(jī)等，來(lái)產(chǎn)生一棵隨機(jī)二叉樹(shù)，如圖4所示。

圖4

自然界不都是二叉樹(shù)，那我們需要加入分支的數(shù)量。原結(jié)構(gòu)中只有兩棵子樹(shù)，現(xiàn)在可能有2棵、3棵甚至更多，可以用循環(huán)的方式解決，來(lái)產(chǎn)生隨機(jī)樹(shù)，使得畫(huà)出來(lái)的樹(shù)更有真實(shí)感。

在我們生活中類似的情況還有不少，典型的如Koch曲線，數(shù)字旋轉(zhuǎn)方陣也是一類典型的遞歸應(yīng)用。（學(xué)會(huì)從中發(fā)現(xiàn)相似性）

5 結(jié)束語(yǔ)

如何用遞歸思想解決實(shí)際問(wèn)題，確定問(wèn)題的可分解性，分析遞歸模型的基本結(jié)構(gòu)。

算法實(shí)現(xiàn) ：if（…）{… …} else {… …}