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部落格
上一篇:火力不足恐懼症的表現都有什麼?