李海磊

（江蘇省南通市海門市海門中學，江蘇海門 226100）

引 言

人工智能的快速發(fā)展已經(jīng)越來越多地影響著我們的生活，搶占人工智能發(fā)展的制高點關乎國運及民族未來。我國人工智能最后能發(fā)展到什么樣的高度，取決于我們能培養(yǎng)和發(fā)展出什么樣的人才。

中學階段的信息技術教學必須能夠圍繞這個大目標，緊隨時代發(fā)展的需要，積極改革。2010年，陳國良院士在一次報告中提出的“計算思維培養(yǎng)”應該作為計算機基礎課程教學改革的一個重點。因此，信息技術課堂在教授學生基本技能的同時，更要把培養(yǎng)學生的計算思維置于一個前所未有的高度。中學生計算思維的培養(yǎng)不能只停留在口號上，而應該從課上課下的每一個概念、算法、程序細節(jié)的講解和訓練等方面入手，夯實基礎，一步一個腳印、踏踏實實地提高學生的程序設計能力。

而在眾多需要掌握的編程技巧中，“遞歸”不但是學生必須掌握的基本知識點，更是一種抽象和分析問題的模式。本文試著從教學實踐的角度來談談如何輔助學生更快更好地理解“遞歸”編程方法（基于C/C++語言）。

一、函數(shù)調用的基本過程

其實，“遞歸”從程序運行的角度來說就是函數(shù)調用，因此準確理解普通函數(shù)之間的調用過程有助于理解函數(shù)“遞歸”調用的本質。

在設計程序解決問題時，為了減少編程難度和問題規(guī)模的可控，需要把大的問題和模塊分解成若干子問題或者子模塊，而這些子問題、子模塊的求解往往是通過函數(shù)這個載體來實現(xiàn)的，這就必然會涉及函數(shù)之間的調用。清晰、準確地理解函數(shù)調用過程至關重要，但對于沒有編程基礎的中學生來說，這是一個比較困難的事情。更可行的辦法莫過于從現(xiàn)實生活的應用實例出發(fā)，以可視化的方式來描繪、講解函數(shù)調用過程[1]。

例如，在處理一篇學習資料時，中途遇到不理解的內容需要求助于其他方面的資料，就可以暫停原來的任務，轉而去執(zhí)行求助任務，等求助過程結束后再返回到原來任務的中斷處，原任務重新啟動并繼續(xù)處理下去。這個過程大致分為以下幾個階段：（1）中斷原來任務時，要在相應的地方做一個“標識”，目的是方便以后的任務重啟。（2）在求助其他資料之前，往往需要提煉資料中的相關內容。簡單地說，就是要做好帶著“問題”去求助的準備。（3）求助任務開始執(zhí)行，生成結果并返回。（4）回到原來的“標識”處，原先暫時中斷的任務重新啟動并繼續(xù)執(zhí)行下去。

函數(shù)的調用過程和上面的例子比較相似，例如，在主函數(shù)main( )中需要調用函數(shù)f( )，執(zhí)行過程大致如下：（1）主調函數(shù)，也就是main( )函數(shù)，在調用f( )前也要做好“標識”工作，即保存當前現(xiàn)場，保存返回地址。（2）調用f( )函數(shù)，控制權交給f( )。（3）f( )執(zhí)行并返回。（4）恢復主調函數(shù)的調用現(xiàn)場，恢復返回地址。至此，調用f( )的工作完成，主調函數(shù)根據(jù)恢復地址繼續(xù)執(zhí)行下去。調用過程如圖1所示。

圖1 調用過程

二、函數(shù)的遞歸調用

函數(shù)的遞歸調用就是直接或間接調用自己的過程。其本質和普通函數(shù)之間的調用并無二致，但是因為其特有的自己調用自己的特性，往往會使得學生在理解上產(chǎn)生困惑和混淆。例如，有的學生會把遞歸誤解成循環(huán)或者函數(shù)復制。教學實踐中發(fā)現(xiàn)，如果教學案例選擇設計得當，并配合準確的表述和可視化的圖解，那么幫助學生準確理解遞歸執(zhí)行過程的目的是完全可以達到的[2]。

試舉一例，要求整數(shù)n的階乘。已知：

現(xiàn)在定義函數(shù)f(n)來求解n！。參考代碼如下：

main( )函數(shù)中調用f(n)時，把3賦值給了參數(shù)n，之后f(n)進行了若干次遞歸調用，遞歸到邊界之后便停止此過程，然后開啟了返回結果的過程?，F(xiàn)在把該代碼的執(zhí)行過程簡單圖解，如圖2所示。

最終f(n)函數(shù)返回主調函數(shù)main( )時，返回值是6，并賦值給s。

圖2 代碼執(zhí)行過程圖解

總結圖2可知：（1）遞歸調用首先會發(fā)生一系列不斷自我調用的過程，也就是不斷向邊界逼近的過程。（2）遞歸一定要有邊界，也就是遞歸到某個狀態(tài)時就會得到結果，此后遞歸調用不再繼續(xù)。（3）遞歸一旦停止就會開始恢復上一層中主調函數(shù)的調用現(xiàn)場，從而實現(xiàn)逆序回歸的過程。從上面的分析可以看出，遞歸絕對不是循環(huán)，每一次遞歸調用并不是把原來的函數(shù)代碼復制一份。遞歸的過程中，計算機系統(tǒng)不斷進行著把調用現(xiàn)場、變量、返回地址等有序保管到堆棧、內存空間中的工作，等遞歸結束之后又通過出棧的方式把主調現(xiàn)場恢復，然后逐步返回。

三、遞歸思想應用一般方法

使用遞歸思想來設計算法是有其特殊的優(yōu)點的。例如，會使程序簡潔明了、易讀易寫、結構簡單等。但是遞歸方法不能包打一切，是有適用的場合的。以上例中求n！為例，求f(n)的問題可以轉成求f(n-1)的問題，而且可以不斷地轉變下去。這樣的轉變之所以能成立，是因為轉變前后問題的本質是一樣的，算法思想是一致的，只是求解的數(shù)據(jù)規(guī)模不同而已。轉變的過程就是把問題的規(guī)模不斷縮小的過程，當然轉變不能無限制地進行下去，它肯定會遇到一個臨界點，在這個臨界點程序會生成一個初始結果，然后系統(tǒng)會掉轉方向，回溯過去，最后得解。也就是說，能使用遞歸的方法解決的問題必須要符合下面的條件：（1）能夠設計出表達式把原問題轉變成子問題。（2）子問題的規(guī)模比原問題要小。（3）子問題可以通過表達式轉變成子問題或者因為遞推到邊界而直接得解。（4）通過整合子問題的解，能夠回溯推出原問題的解。

試舉一例，求整數(shù)m，n（m＞n）的最大公約數(shù)。小學數(shù)學中就有此類問題的解法，簡單來說，就是把兩數(shù)的公有質因數(shù)求解出來并相乘，便可得出最大公約數(shù)。但這個算法不適用遞歸思想，一方面，它很難做到規(guī)模更??；另一方面，它很難用同樣的表達式求解子問題。

此外，著名的歐幾里得定理也能解決求最大公約數(shù)（gcd）的問題。它的公式是這樣的：

gcd(m,n)=gcd(n,r)，r=m%n，（m＞n,m,n,r都是整數(shù)），當r=0時，n的值就是解。

分析：（1）原問題的m、n的規(guī)模較大，而子問題n、r的規(guī)模明顯變小。（2）原問題和子問題的求解表達式是一致的。（3）存在遞歸邊界，即r=0時便可以求得解。可以看出該定理的本身就是遞歸的，因此，使用遞歸的方法來設計并編寫程序就是順理成章的了。參考代碼如下：

綜合前面幾個例子，可以非常明顯地看出使用遞歸思想設計出來的程序簡潔優(yōu)美。但是矛盾是無處不在的，遞歸在保證優(yōu)美的同時付出的代價是系統(tǒng)開銷增大，執(zhí)行速度變慢，因此即便是能使用遞歸的場合也要謹慎使用。

結 語

本文站在實際教學的角度，分析了學生在學習和使用遞歸方法上存在的困難，并給出了解決辦法。遞歸是一個非常好的編程方法，也是一種很棒的解決問題的模式。教育教學方法的探索和創(chuàng)新是無止境的，如何準確把握學生在信息學習上遇到的困難和思維盲點并給出有效的解決方案，是值得每一個教師認真研究的。同時，我們要把這些研究、探索和新一輪的信息技術課程改革中提出的培養(yǎng)學生的計算思維的目標有效結合起來，始終緊扣時代主題，從學生終身發(fā)展的戰(zhàn)略高度出發(fā)，努力提高學生的程序設計水平和解決問題的能力。