□屠新兵

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

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

□屠新兵

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

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

C語言；遞歸

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

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

1 遞歸的編程方法

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

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

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

2 遞歸程序的閱讀

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

分析：這條題目的考點(diǎn)是大家對(duì)遞歸過程的了解情況，函數(shù)ab()有兩個(gè)分支，第一個(gè)分支是當(dāng)y的值為0時(shí)，輸出x,這是遞歸的出口；另一個(gè)分支是調(diào)用自己，并輸出x和y。輸出結(jié)果的先后順序是遞歸的難點(diǎn)，考生往往容易出錯(cuò)，程序閱讀題，閱卷老師通常是按行給分，一旦輸出順序出錯(cuò)，就會(huì)失分。那么如何理解，才能不失分？閱讀程序從主函數(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áng)州市邗江中等專業(yè)學(xué)校綜合高中部主任,一級(jí)教師,研究方向：計(jì)算機(jī)教學(xué)。