□屠新兵

(揚州市邗江中等專業(yè)學(xué)校江蘇揚州225009)

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

□屠新兵

(揚州市邗江中等專業(yè)學(xué)校江蘇揚州225009)

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

C語言；遞歸

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

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

1 遞歸的編程方法

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

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

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

2 遞歸程序的閱讀

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

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

1004-7026（2016）12-0114-02

TP182

A

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

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