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

楊 嬌

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

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

1 遞歸的重要性

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

2 遞歸知識的構建

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

3 講授過程中的指導思想

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

4 遞歸知識點教學內容與方法設計

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

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

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

圖1

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

4.2 現實生活問題如何轉化為數學問題的遞歸

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

n-1級臺階與n級臺階的問題具有相似性，只是規模相對較小。假設上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數列。這個數列的實現代碼和n！結構一樣，幾乎沒有區別，我們暫且先放下。

圖2

圖3

4.3 用遞歸算法來實現現實中的遞歸之美

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

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

4.4 陷阱設置無遞歸出口

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

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

圖4

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

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

5 結束語

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

算法實現 ：if（…）{… …} else {… …}