遞歸思想及其算法設計的探討

楊 嬌

（陸軍步兵學院計算機教研室，南昌 330103）

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

1 遞歸的重要性

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

2 遞歸知識的構建

掌握構建關于遞歸的知識結構的概念，訓練學員逆向思維、計算思維，培養(yǎng)用遞歸思想分析和解決較復雜問題能力。

3 講授過程中的指導思想

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

4 遞歸知識點教學內(nèi)容與方法設計

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

4.1 通過視覺遞歸圖片、故事、數(shù)學問題將學員快速帶入到遞歸

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

圖1

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

4.2 現(xiàn)實生活問題如何轉化為數(shù)學問題的遞歸

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

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

圖2

圖3

4.3 用遞歸算法來實現(xiàn)現(xiàn)實中的遞歸之美

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

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

4.4 陷阱設置無遞歸出口

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

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

圖4

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

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

5 結束語

如何用遞歸思想解決實際問題，確定問題的可分解性，分析遞歸模型的基本結構。

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