The best time to plant a tree was 10 years ago. The second best time is now
翻譯：種一棵樹最好的時間是十年前,其次是現在
所謂運氣，不過是機會碰巧遇到了你的努力
本章內容是對遞回詳細講解，中間穿插了較多的遞回經典案例，方便我們理解遞回的思想以及使用遞回去解決實際的問題，
文章目錄
- 1、函式遞回
- 練習1 : (畫圖講解)
- 練習2∶（畫圖講解)
- 練習3∶
- 練習4∶
- 2、遞回練習：
- 1、字串逆序：
- 2、數字求和：
- 3、求n的k次方：
1、函式遞回
什么是遞回：程式呼叫自身的編程技巧稱為遞回（recursion），遞回做為一種演算法在程式設計語言中廣泛應用，一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，
遞回的主要思考方式在于 : 把大事化小
注意：函式在呼叫的時候會向記憶體申請空間，（遞回的程序就是函式的不停呼叫程序）
最簡單的遞回函式：主函式呼叫主函式
#include<stdio.h>
int main()
{
printf("hello world\n");
main();
return 0;
}
上述代碼結果：死回圈，堆疊溢位（stack overflow)
為什么會出現堆疊溢位呢？
要想搞懂堆疊溢位的原因，首先我們要明白程式運行程序中記憶體的劃分磁區
每一次函式的呼叫，都需要在堆疊區分配一定的空間（也就是說函式呼叫也在堆疊區開辟空間），呼叫次數太多，堆疊空間不夠分配（被耗干），導致堆疊溢位，
練習1 : (畫圖講解)
接受一個整型值（無符號），按照順序列印它的每一位，例如︰輸入∶1234，輸出1234.
要順序列印它的每一位，就需要得到它的每一位，1234最容易得到的就是個位
1234 % 10 = 4
1234 / 10 = 123 % 10 = 3
123 / 10 = 12 % 10 = 2
12 / 10 = 1 % 10 = 1
1 / 10 = 0
#include<stdio.h>
void print(int n)
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf("%d", &num);//1234
print(num);//列印1 2 3 4
//print(1234)
//print(123) 4
//print(12) 3 4
//print(1) 2 3 4
// 1 2 3 4
//當（）里面的數字大于9的時候就拆分，小于9，為個位數的時候停止拆分，進行列印
return 0;
}
畫圖詳解：
比較上面兩個遞回函式，我們可以看到： 遞回的兩個必要條件
①存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
②每次遞回呼叫之后越來越接近這個限制條件，
注意：這兩個條件是必要條件，不是充分條件，也就是說遞回函式一定滿足這兩個條件，但是滿足這兩個條件不一定是遞回，看下面這個例子：
按F10進行除錯：
每一次函式的呼叫，都需要在堆疊區分配一定的空間，呼叫次數太多，堆疊空間不夠分配（被耗干），導致堆疊溢位，
所以我們在寫遞回代碼的時候，一定要注意以下幾點：
1、不能死遞回，要有跳出條件，每次遞回逼近跳出條件
2、遞回層層不能太深
練習2∶（畫圖講解)
撰寫函式不允許創建臨時變數，求字串的長度，
初步解題思路：
#include<stdio.h>
#include<string.h>
//求字串長度
int my_strlen(char* pr)
{
int count = 0;
while (*pr != '\0')
{
count++;
pr++;
}
return count;
}
int main()
{
char arr1[] = "bit";
//int len = strlen(arr1);//求字串長度
int len = my_strlen(arr1);
//arr1是陣列，陣列傳參，傳過去的不是整個陣列，而是首元素的地址
printf("%d\n", len);
return 0;
}
這種方式雖然計算出字串的長度，但是創建了一個臨時變數count，現在使用遞回的方式來實作：
int my_strlen(char* pr)
{
if (*pr != '\0')
return 1 + my_strlen(pr + 1);
else
return 0;
}
//把大事化小
//my_strlen("bit")
//1+my_strlen("it")
//1+1+my_strlen("t")
//1+1+1+my_strlen("\0")
//1+1+1+0 = 3
畫圖詳解：
練習3∶
求n的階乘，(不考慮溢位)
#include<stdio.h>
#include<string.h>
int Fun1(int x)//迭代（回圈）實作
{
int i = 0;
int y = 1;
for (i = 1; i <= x; i++)
{
y = y * i;
}
return y;
}
int Fun2(int x)//遞回實作
{
if (x > 1)
return x * Fun2(x - 1);
else
return 1;
}
int main()
{
int n = 0;
int ret = 0;
printf("請輸入一個數:>>\n");
scanf("%d", &n);
//ret = Fun1(n);//回圈的方式
ret = Fun2(n);//遞回的方式
printf("%d的階乘為：%d\n", n, ret);
return 0;
}
練習4∶
求第n個斐波那契數，（不考慮溢位)
#include<stdio.h>
int count = 0;
int Fib1(int x)//遞回實作
{
if (x == 3)
count++;
if (x <= 2)
return 1;
else
return Fib1(x - 1) + Fib1(x - 2);
}
int Fib2(int x)//函式實作
{
int a = 1;
int b = 1;
int c = 1;
while (x > 2)
{
c = a + b;
a = b;
b = c;
x--;
count++;
}
return c;
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
//ret = Fib1(n);//求第n個斐波那契數
ret = Fib2(n);//回圈實作
printf("%d\n", ret);
printf("count = %d\n", count);
return 0;
}
我們在主函式里面寫后續要被呼叫的某個函式的時候，先假設要用這個函式實作什么功能，直接去用，之后再去真正定義并實作這個函式，
這種思想叫做：TDD - 測驗驅動開發 先去想函式怎么用，然后再實作，
遞回結果：
遞回方式：
回圈結果：
可以看出此時使用遞回方式并不高效，其計算同一個數比如 3 的次數為 2 ^ n （遞回方式）
而使用回圈方式(n > 3時) 次數為 n - 2
那我們如何改進呢 ?
在除錯factorial函式的時候，如果你的引數比較大，那就會報錯 : stack overflow(堆疊溢位）這樣的資訊，系統分配給程式的堆疊空間是有限的，但是如果出現了死回圈，或者（死遞回)，這樣有可能導致一直開辟堆疊空間，最終產生堆疊空間耗盡的情況，這樣的現象我們稱為堆疊溢位，那如何解決上述的問題 ？
1.將遞回改寫成非遞回，
⒉使用static物件替代nonstatic區域物件，在遞回函式設計中，可以使用static物件替代nonstatic區域物件（即堆疊物件），這不僅可以減少每次遞回呼叫和回傳時產生和釋放nonstatic物件的開銷，而且static物件還可以保存遞回呼叫的中間狀態，并且可為各個呼叫層所訪問，
提示∶
1.許多問題是以遞回的形式進行解釋的，這只是因為它比非遞回的形式更為清晰，
2. 但是這些問題的迭代實作往往比遞回H實作效率更高，雖然代碼的可讀性稍微差些，
3.當一個問題相當復雜，難以用迭代實作時，此時遞回實作的簡潔性便可以補償它所帶來的運行時開銷，
2、遞回練習：
1、字串逆序：
撰寫一個函式 reverse_string(char* string)（遞回實作）
實作：將引數字串中的字符反向排列，不是逆序列印，
要求：不能使用C函式庫中的字串操作函式，
比如 : char arr[] = “abcdef”，逆序之后陣列的內容變成：fedcba
#include<stdio.h>
//#include<string.h>
//int my_strlen(char* str)//非遞回方法求字串長度
//{
// int count = 0;
// while (*str != '\0')
// {
// count++;
// str++;
// }
// return count;
//}
int my_strlen(char* str)//遞回方法求字串長度
{
if (*str != '\0')
return 1 + my_strlen(str + 1);
else
return 0;
}
//void reverse_string(char* str)//非遞回方法逆序字串
//{
// //int len = strlen(str);
// int len = my_strlen(str);
// int left = 0;
// int right = len - 1;
// while (left < right)
// {
// char tmp = *(str+left);
// *(str + left) = *(str + right);
// *(str + right) = tmp;
// left++;
// right--;
// }
//
//}
void reverse_string(char* str)
{
int len = my_strlen(str);
if (len > 1)
{
char tmp = *str;
*str = *(str + len - 1);
*(str + len - 1) = '\0';
reverse_string(str + 1);
*(str + len - 1) = tmp;
}
}
int main()
{
char arr[] = "abcdefjh";
printf("逆序前：%s\n", arr);
reverse_string(arr);
printf("逆序后：%s\n", arr);
return 0;
}
2、數字求和：
寫一個遞回函式DigitSum(n)，輸入一個非負整數，回傳組成它的數字之和
例如，呼叫DigitSum(1729)，則應該回傳1 + 7 + 2 + 9，它的和是19
例如輸入：1729，輸出：19
思路：大事化小，個位數的9最容易拿下來
#include<stdio.h>
int DigitSum(int n)
{
if (n > 9)
{
return DigitSum(n / 10) + n % 10;
}
else
{
return n;
}
}
int main()
{
int num = 1729;
int sum = DigitSum(num);
printf("%d\n", sum);
return 0;
}
3、求n的k次方：
撰寫一個函式實作n的k次方，使用遞回實作，
#include<stdio.h>
double my_pow(int n, int k)
{
if (k > 0)
{
return n * my_pow(n, k - 1);
}
else if (k == 0)
{
return 1;
}
else
{
return 1.0 / my_pow(n, -k);
}
}
int main()
{
int n = 0;
int k = 0;
double ret = 0.0;
scanf("%d%d", &n, &k);
ret = my_pow(n, k);
printf("%lf\n", ret);
return 0;
}
遞回的擴展：
經典題目：
1、漢諾塔問題
2、青蛙跳臺階問題
下篇關于遞回進階的文章會詳細講到這兩個題目的思路+編程代碼，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279632.html
標籤：其他
上一篇：堆（Heap）的基本知識和堆排序