楊新宇 蘭全祥

摘要：函數(shù)以及函數(shù)的遞歸調(diào)用是學(xué)習(xí)C語(yǔ)言必須要掌握的內(nèi)容，且遞歸作為經(jīng)典的算法思想被廣泛應(yīng)用于程序設(shè)計(jì)中。從應(yīng)用場(chǎng)景的角度出發(fā)，對(duì)C語(yǔ)言中遞歸的定義、特征以及適用場(chǎng)景進(jìn)行了探討，并對(duì)這些適用場(chǎng)景進(jìn)行分析和舉例。最后，分析并探討了遞歸的優(yōu)缺點(diǎn)，并給出了遞歸的優(yōu)化方法和將遞歸轉(zhuǎn)換為非遞歸的方法。

關(guān)鍵詞：C語(yǔ)言;遞歸;應(yīng)用;非遞歸化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）22-0237-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（0SID）：

1 背景

隨著時(shí)代的進(jìn)步以及計(jì)算機(jī)編程語(yǔ)言的不斷發(fā)展，從20世紀(jì)80年代傳承至今的C語(yǔ)言始終是各大高校首選的計(jì)算機(jī)編程語(yǔ)言。世界編程語(yǔ)言排行榜（ TIOBE）中C語(yǔ)言的熱門程度自2002年至今始終穩(wěn)居前三[1]。由此可見(jiàn)，C語(yǔ)言的重要程度以及熱門度。另外，模塊化設(shè)計(jì)是所有程序設(shè)計(jì)必須遵循的設(shè)計(jì)原則，而函數(shù)就是C語(yǔ)言模塊化的重要組成部分[2]。C語(yǔ)言函數(shù)以及函數(shù)的使用是學(xué)習(xí)C語(yǔ)言必須要掌握的內(nèi)容。遞歸作為經(jīng)典的函數(shù)使用方法，應(yīng)用范圍廣泛，是函數(shù)中不可或缺的重要內(nèi)容，也是作為一個(gè)開(kāi)發(fā)者應(yīng)該掌握的重要算法之一。

2 遞歸的概述

2.1 定義

張長(zhǎng)海等人認(rèn)為在定義一個(gè)函數(shù)時(shí)，若在定義函數(shù)的內(nèi)部又出現(xiàn)對(duì)函數(shù)本身的調(diào)用，則稱該函數(shù)是遞歸的或遞歸定義的[3];譚浩強(qiáng)等人認(rèn)為遞歸就是函數(shù)自己直接或間接地調(diào)用自身的過(guò)程[4];丁雪晶認(rèn)為遞歸就是把要解決的問(wèn)題分解成與原問(wèn)題有相同解法，且規(guī)模較小的問(wèn)題，直到遇見(jiàn)終止條件[5]。綜上，筆者認(rèn)為函數(shù)的遞歸就是直接或間接地調(diào)用自身進(jìn)行人棧操作，遇到邊界之后再進(jìn)行出棧的過(guò)程，且在人棧過(guò)程中，由原始問(wèn)題分解為的子問(wèn)題始終向邊界靠攏。

2.2 特征

從上述定義可得出遞歸的以下特征：

1）函數(shù)總是直接或者間接的調(diào)用自身;

2）函數(shù)的遞歸必須有結(jié)束條件（即問(wèn)題的邊界），且在調(diào)用的過(guò)程中始終向某一個(gè)邊界靠近;

3）遞歸過(guò)程是一個(gè)不斷人棧和出棧的過(guò)程。

2.3 應(yīng)用場(chǎng)景

遞歸的本質(zhì)是將關(guān)于n的問(wèn)題轉(zhuǎn)化為同類解法的關(guān)于m的問(wèn)題，其中n和m是問(wèn)題的規(guī)模，且m比n更靠近問(wèn)題的邊界（遞歸結(jié)束條件）。

通過(guò)對(duì)常見(jiàn)遞歸應(yīng)用的分析，筆者將遞歸應(yīng)用場(chǎng)景分為三類：

1）數(shù)據(jù)的初始化是遞歸的。

2）數(shù)據(jù)的結(jié)構(gòu)是遞歸的。

3）問(wèn)題的求解是遞歸的。

3 遞歸的案例

根據(jù)上述對(duì)函數(shù)遞歸的定義、特征以及應(yīng)用場(chǎng)景的總結(jié)，本文對(duì)上述遞歸的應(yīng)用場(chǎng)景進(jìn)行分析和舉例。

3.1 數(shù)據(jù)的初始化是遞歸的

示例：Fibonacci數(shù)列（兔子數(shù)列）

描述：形如1，1，2，3，5，8，13，21I.….的數(shù)列被稱為Fibonac-Cl數(shù)列，即第n個(gè)數(shù)等于第n-l個(gè)數(shù)和第n-2個(gè)數(shù)之和。

分析：根據(jù)上述定義，對(duì)數(shù)列進(jìn)行數(shù)學(xué)歸納可得出數(shù)學(xué)遞推公式。

根據(jù)分析可知，F(xiàn)ibonacci數(shù)列是典型的數(shù)據(jù)的初始化是遞歸的例子，即要對(duì)n進(jìn)行初始化，必須知道n-l和n-2的值。

初始化Fibonacci數(shù)列的關(guān)鍵代碼如下：

int Fib（int n）{

if（n ==1¨n==2）{return 1;）

elsef

return Fib（n-I）+Fib（n-2）;

）

）

3.2 數(shù)據(jù)的結(jié)構(gòu)是遞歸的

示例：二叉樹

描述：二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩棵互不相交的稱為該根的左子樹和右子樹的二叉樹組成[6]。

分析：由定義可知，一個(gè)根結(jié)點(diǎn)可能存在左子樹和右子樹，且左子樹和右子樹又是一顆更小的二叉樹。

因此，二叉樹從數(shù)據(jù)結(jié)構(gòu)上來(lái)看是遞歸的，如圖1所示，A的左子樹、A的右子樹以及C的左子樹都是一顆二叉樹，且無(wú)論是二叉樹的初始化還是遍歷都能用遞歸來(lái)解決。

構(gòu)造二叉樹的關(guān)鍵代碼如下：

typedef struct BiTNode{char data; struct BiTNode，*rchild，*rchild;}BiTNode，a：BiTree;

void CreateBiTree（BiTiree *T）{

char c;scanf（”%c”，&c）;

i“c==7#7）{*T=NULL;】

elsef

*T= （BiTNode*）new BiTNode;

（*T）->data=c;

CreateBiTree（&（*T）->lchild）;

CreateBiTree（&（*T）->rchild）;

）

】

由代碼可以看出，在二叉樹的構(gòu)造中，輸入根節(jié)點(diǎn)數(shù)據(jù)之后還需要遞歸調(diào)用CreateBiTree函數(shù)對(duì)其左右子樹進(jìn)行構(gòu)造，即要成功構(gòu)造一顆二叉樹，需要先構(gòu)造出其左、右子樹。另外，二叉樹的遍歷也可采用遞歸的方法實(shí)現(xiàn)先序遍歷、中序遍歷與后序遍歷。

3.3 問(wèn)題的求解是遞歸的

示例：漢諾塔

描述：現(xiàn)有A，B，C三根柱子，在A柱有n個(gè)從上到下面積依次增大的盤子，現(xiàn)在想把A柱這n個(gè)盤子移動(dòng)到C柱，但規(guī)定每一次只能移動(dòng)一個(gè)盤子，且三根柱子的盤子始終都保持著面積大的盤子在下，面積小的盤子在上，問(wèn)盤子移動(dòng)的步驟。