探究遞歸思想 提高學生計算思維能力

李海磊

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

引 言

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

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

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

一、函數調用的基本過程

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

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

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

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

圖1 調用過程

二、函數的遞歸調用

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

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

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

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

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

圖2 代碼執行過程圖解

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

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

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

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

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

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

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

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

結 語

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