C語言中遞歸的分析及應(yīng)用

楊新宇 蘭全祥

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

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

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

文章編號：1009-3044（2020）22-0237-02

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

1 背景

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

2 遞歸的概述

2.1 定義

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

2.2 特征

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

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

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

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

2.3 應(yīng)用場景

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

通過對常見遞歸應(yīng)用的分析，筆者將遞歸應(yīng)用場景分為三類：

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

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

3）問題的求解是遞歸的。

3 遞歸的案例

根據(jù)上述對函數(shù)遞歸的定義、特征以及應(yīng)用場景的總結(jié)，本文對上述遞歸的應(yī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ù)上述定義，對數(shù)列進(jìn)行數(shù)學(xué)歸納可得出數(shù)學(xué)遞推公式。

根據(jù)分析可知，F(xiàn)ibonacci數(shù)列是典型的數(shù)據(jù)的初始化是遞歸的例子，即要對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)上來看是遞歸的，如圖1所示，A的左子樹、A的右子樹以及C的左子樹都是一顆二叉樹，且無論是二叉樹的初始化還是遍歷都能用遞歸來解決。

構(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ù)對其左右子樹進(jìn)行構(gòu)造，即要成功構(gòu)造一顆二叉樹，需要先構(gòu)造出其左、右子樹。另外，二叉樹的遍歷也可采用遞歸的方法實(shí)現(xiàn)先序遍歷、中序遍歷與后序遍歷。

3.3 問題的求解是遞歸的

示例：漢諾塔

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