程式設計師必須掌握的遞迴演算法

1 引言

程式呼叫自身的程式設計技巧稱為遞迴（ recursion）

。遞迴作為一種演算法在程式設計語言中廣泛應用。一個方法或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的程式碼量。

例如求和問題：若要求解

S

100

= 1 + 2 + 3 + 4 + …. + 100

的值，透過迴圈的方式程式碼如下：

int sum = 0；for （int i = 1； i <= 100； i++） { sum = sum + i；}

透過遞迴方式是如何求解呢？由 **1 + 2 + 3 + 4 + …。 + 100 **可以分解為

( 1 + 2 + 3 + 4 + …. + 99) + 100

，可以看出

S

100

= S

99

+ 100

，可以得出

S

n

= S

n-1

+ n

。透過遞迴的方式程式碼如下：

public int sum（int n） { if （n == 1） { return 1； } else { return sum（n - 1） + n； }}

透過遞迴程式碼可以看出，sum（） 方法中又呼叫了其自身，只是將傳入的引數發生改變。這種程式呼叫自身的方式就是遞迴。

2 應用場景

什麼樣的問題才可以使用遞迴的方式求解呢？構成遞迴需要具備兩個條件：

（1）子問題與原始問題為同樣的事情，二者的求解方法是相同的，且子問題比原始問題更易求解。

（2）遞迴不能無限制地呼叫本身，必須有個遞迴出口。遞迴出口對應的情形相對簡單，可以化簡為非遞迴狀況處理。

3 例項

3。1 斐波那契數列

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：

1、1、2、3、5、8、13、21、34、……

在數學上，斐波納契數列以如下被以遞推的方法定義：

F(1)=1，F(2)=1,，F(n) = F(n-1) + F(n-2)（n>=3，n∈N*）

。

問題分析：

斐波那契數列的對於原問題F（n）的求解可以轉為對F（n-1）、F（n-2）兩個子問題的求解，故符合條件（1）。由F（1）=1，F（2）=1，可以得出斐波那契數列問題是有遞迴出口的，遞迴出口對應F（1） = 1，F（2） = 1。求解斐波那契數列的程式碼如下：

public class FibonacciSequence { public static void main（String［］ args）{ System。out。println（Fribonacci（9））； } public static int Fribonacci（int n）{ if（n <= 2） return 1； else return Fribonacci（n-1）+Fribonacci（n-2）； }}

3。2 階乘問題

階乘問題的數學表示式為：

n! = n * (n-1) * (n-2) * …* 1 (n>0)

。透過分析可以得出

n! = (n-1)! * n

。令

F(n) = n!

，則

F(n) = F(n-1) * n

。則階乘問題符合條件（1）。由

0! = 1

，可以得出

F(0) = 1

。則階乘問題符合條件（2），遞迴出口為

F(0) = 1

。利用遞迴求解階乘問題程式碼如下：

int factorial（int n）{ int sum = 0； if （0 == n） return 1； else sum = n * factorial（n-1）； return sum；}

3。3 樹的遍歷

對於樹遍歷問題在之前樹的專題中已經詳細介紹，這裡不再贅述。二叉樹的遍歷程式碼如下：

/*前序遍歷演算法*/void PreOderTraverse（BiTree T）{ if（T == NULL） return； printf（“%c”，T->data）； //顯示結點資料，可以更改為其他對結點操作 PreOderTraverse（T->lchild）； //先遍歷左子樹 PreOderTraverse（T->rchild）； //最後遍歷右子樹 } /*中序遍歷遞迴演算法*/void InOderTraverse（BiTree T）{ if（T == NULL） return ； InOderTraverse（T->lchild）； //中序遍歷左子樹 printf（“%c”，T->data）； //顯示結點資料，可以更改為其他對結點的操作 InOderTraverse（T->rchild）； //最後中序遍歷右子樹 } /*後序遍歷遞迴演算法*/void PostOderTraverse（T）{ if（T==NULL） return； PostOderTraverse（T->lchild）； //先遍歷左子樹 PostsOderTraverse（T->rchild）； //再遍歷右子樹 printf（“%c”，T->data）； //顯示結點數可以更改為其他對結點資料 }

透過程式碼可以看出，二叉樹的遍歷過程使用遞迴方式實現既有助於理解，又簡化了程式碼量。

4 結語

使用遞迴求解問題就好比，你手中有一把鑰匙想要開啟一扇門。當你打開面前這扇門，看到屋裡面還有一扇門。你走過去，發現手中的鑰匙還可以開啟它，你推開門，發現裡面還有一扇門，你繼續開啟它。若干次之後，你打開面前的門後，發現只有一間屋子，沒有門了。然後，你開始原路返回，每走回一間屋子，你數一次，走到入口的時候，你可以回答出你到底用這你把鑰匙打開了幾扇門。

遞迴演算法的應用十分廣泛，應用遞迴演算法可以使你的程式碼根據“優雅”。