C語言——遞迴演算法

一、什麼是遞迴

簡單來說遞迴是一個函式直接或者間接的呼叫自身的一種方法，他通常將一個大型問題層層裝換為相似的規模較小的問題來求解。

舉個例子：比如在字典中查詢一個詞語，當查到這個詞的解釋後，發現他所給的解釋出現了不懂的詞語，那麼我就需要繼續查詢，一直查詢到懂了為止，當查詢結束後，也就相當於遞迴結束了。

用遞迴解決問題需要具備哪些條件？

遞迴的表示式，也可以 來理解為你發現的規律；

遞迴出口，也可以理解為必須有一個明確的結束條件；

注意：遞迴的目的是為了讓問題的規模變小，遞迴層次過多會導致棧溢位，且效率不高

再舉個反面例子，從前有座山，山裡有座廟，廟裡有個老和尚會講故事，講的什麼故事啊？講的是從前有座山，山裡有座廟，廟裡有個老和尚會講故事，講的什麼故事啊？從前有座山，山裡有座廟，廟裡有個老和尚會講故事，講的什麼故事啊？

這是個典型的反面教材，想到那個魚遞迴找不到終止條件，就會產生死迴圈；

二、遞迴的幾個經典題目

1。 斐波那契數列

斐波那契數列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次類推下去，你會發現，它後一個數等於前面兩個數的和。在這個數列中的數字，就被稱為斐波那契數。

那麼用遞迴的方法怎麼求解呢？

/*

迭代法

*/

void fun_1（）

{

static int n = 0；//索引變數

static int a_ary［40］；

a_ary［0］ = 0；//n=0；

a_ary［1］ = 1；//n=1；

a_ary［2］ = 1；//n=2；

a_ary［3］ = 2；//n=3；

a_ary［4］ = 3；//n=4；

a_ary［5］ = 5；//n=5；

a_ary［6］ = 8；//n=6；

// 。。。

​

for （n = 2； n < 40； n++）

{

a_ary［n］ = a_ary［n-1］ + a_ary［n-2］；

printf（“%d\r\n”， a_ary［n］）；

}

}

/*

遞迴法

*/

int fun_2（int n）

{

if （n <= 1） //遞迴出口

return n；

else

return fun_2（n - 1） + fun_2（n - 2）；//向遞迴出口方向靠近自身的呼叫

}

很好看出規律，規律就是當前項等於前兩項的和；

2。 倒敘列印字串

//倒敘列印字串

void print_str_reverse（char *str）

{

if （！*str）

return；

print_str_reverse（str + 1）；

​

putchar（*str）；

}

傳為引數為一個char型指標，並且每進入一次函式就判斷一次當前指標為空指標，如果當前指標為空指標說明已經已經指向字串尾部，此時return到上一層函式列印輸出，由於棧的特點是先進後出的所以列印字元的時候是倒敘的。

3。 n的階乘n！

n！一共分為兩種情況

n=0 n！=1

n>0 n*（n-1）

int fun_3（int n）

{

if （n==0）

{

return 1；

}

else if （n>0）

{

return n * fun_3（n - 1）；

}

————————————————

版權宣告：本文為CSDN博主「瘋小瘋」的原創文章，遵循CC 4。0 BY-SA版權協議，轉載請附上原文出處連結及本宣告。

原文連結：C語言——遞迴演算法_c/c++_瘋小瘋的部落格-CSDN部落格