中職C語言中遞歸問題的解決方法探索

□屠新兵

(揚州市邗江中等專業學校江蘇揚州225009)

中職C語言中遞歸問題的解決方法探索

□屠新兵

(揚州市邗江中等專業學校江蘇揚州225009)

遞歸是各類高級語言中的一個重要知識點，如果理解透徹，解決問題就會得心應手，反之會與循環語句混淆，甚至在寫輸出結果時，秩序完全相反。本文主要以C語言為例，介紹一些常見遞歸題目的編程和解決方法，從而加深大家對遞歸的了解。

C語言；遞歸

遞歸就是一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，從而大大地減少程序的代碼量。用遞歸思想寫出的程序往往十分簡潔易懂。

一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段，俗稱為遞推和回歸。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。有兩個注意點：(1)遞歸就是在過程或函數里調用自身；(2)在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。本文主要以兩個常見實例，對遞歸問題的解決方法進行探索，從而加深大家對遞歸的理解。

1 遞歸的編程方法

例1：用遞歸方法編一函數int yh(int m,int n)，打印下圖楊輝三角形。

分析：從楊輝三角形的特點可以知道，左邊一列也就是列坐標為0的時候，值為1，主對角線也就是行列相等的時候，值為1，其它值為上一行的前一列與上一行的同一列之和。由此可以知道，遞歸結束條件就是當列坐標為0或者行列相等的時候，返回1，其它情況調用自身，求得上一行的前一列與上一行的同一列之和。函數如下：

拓展：在實際運用中，有很多這樣的題目，比如：求階乘，求Fibonacci數列，求兩個數的最大公約數，漢諾塔問題等，這類問題都可用遞歸的方法解決。遇到這類題目，要找準兩個注意點：一是遞歸出口，即何時結束；二是自己調用自己，要離結束條件越來越近。把握這兩點，類似的題目便能迎刃而解。

2 遞歸程序的閱讀

例2：閱讀下列題目，寫出輸出結果。

分析：這條題目的考點是大家對遞歸過程的了解情況，函數ab()有兩個分支，第一個分支是當y的值為0時，輸出x,這是遞歸的出口；另一個分支是調用自己，并輸出x和y。輸出結果的先后順序是遞歸的難點，考生往往容易出錯，程序閱讀題，閱卷老師通常是按行給分，一旦輸出順序出錯，就會失分。那么如何理解，才能不失分？閱讀程序從主函數入手，主程序的第一步是輸出a和b的原始值36、24，并調用函數ab(36,24)；由ab(36,24)推出y不為0，做第二步ab(24,12)，并輸出x、y的值為36、24，……依此類推，遞歸調用滿足先調用后結束，后調用先結束，執行過程如圖所示：

1004-7026（2016）12-0114-02

TP182

A

10.16675/j.cnki.cn14-1065/f.2016.12.087

屠新兵（1975.2-），男，江蘇邗江，揚州市邗江中等專業學校綜合高中部主任,一級教師,研究方向：計算機教學。