C語言中遞歸的分析及應用

楊新宇 蘭全祥

摘要：函數以及函數的遞歸調用是學習C語言必須要掌握的內容，且遞歸作為經典的算法思想被廣泛應用于程序設計中。從應用場景的角度出發，對C語言中遞歸的定義、特征以及適用場景進行了探討，并對這些適用場景進行分析和舉例。最后，分析并探討了遞歸的優缺點，并給出了遞歸的優化方法和將遞歸轉換為非遞歸的方法。

關鍵詞：C語言;遞歸;應用;非遞歸化

中圖分類號：TP311 文獻標識碼：A

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

開放科學（資源服務）標識碼（0SID）：

1 背景

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

2 遞歸的概述

2.1 定義

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

2.2 特征

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

1）函數總是直接或者間接的調用自身;

2）函數的遞歸必須有結束條件（即問題的邊界），且在調用的過程中始終向某一個邊界靠近;

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

2.3 應用場景

遞歸的本質是將關于n的問題轉化為同類解法的關于m的問題，其中n和m是問題的規模，且m比n更靠近問題的邊界（遞歸結束條件）。

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

1）數據的初始化是遞歸的。

2）數據的結構是遞歸的。

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

3 遞歸的案例

根據上述對函數遞歸的定義、特征以及應用場景的總結，本文對上述遞歸的應用場景進行分析和舉例。

3.1 數據的初始化是遞歸的

示例：Fibonacci數列（兔子數列）

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

分析：根據上述定義，對數列進行數學歸納可得出數學遞推公式。

根據分析可知，Fibonacci數列是典型的數據的初始化是遞歸的例子，即要對n進行初始化，必須知道n-l和n-2的值。

初始化Fibonacci數列的關鍵代碼如下：

int Fib（int n）{

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

elsef

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

）

）

3.2 數據的結構是遞歸的

示例：二叉樹

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

分析：由定義可知，一個根結點可能存在左子樹和右子樹，且左子樹和右子樹又是一顆更小的二叉樹。

因此，二叉樹從數據結構上來看是遞歸的，如圖1所示，A的左子樹、A的右子樹以及C的左子樹都是一顆二叉樹，且無論是二叉樹的初始化還是遍歷都能用遞歸來解決。

構造二叉樹的關鍵代碼如下：

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）;

）

】

由代碼可以看出，在二叉樹的構造中，輸入根節點數據之后還需要遞歸調用CreateBiTree函數對其左右子樹進行構造，即要成功構造一顆二叉樹，需要先構造出其左、右子樹。另外，二叉樹的遍歷也可采用遞歸的方法實現先序遍歷、中序遍歷與后序遍歷。

3.3 問題的求解是遞歸的

示例：漢諾塔

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