宣告：由于作者水平有限，本文難免有錯誤和不準確之處，本人也很想知道這些錯誤，懇望讀者批評指正，
【聯系方式】1583598623@qq.com
【更新記錄】2021年4月19日（第一次更新 ）
【勘誤記錄】暫無
文章目錄
- 1.什么是函式遞回？
- 遞回的倆個必要條件：
- 例題：根據下面遞回函式：呼叫函式Fun(2)，回傳值是多少
- 例題：按照時序列印一個數
- 2.遞回溢位
- 例題：
- 3.（多練幾次，重在理解）：撰寫函式不允許創建臨時變數，求字串長度，
- 4.遞回與迭代
- 例題1：求n的階乘
- 例題2：求第n個斐波那契數0、1、1、2、3、5、8、13、21、34
- 5.漢諾塔問題（假設有24個盤子）
- 6.青蛙跳臺階問題（類似斐波那契數列）
- 7.撰寫一個函式 reverse_string(char \* string)（遞回實作）
- 8.寫一個遞回函式DigitSum(n)，輸入一個非負整數，回傳組成它的數字之和
1.什么是函式遞回？
程式呼叫自身的編程技巧稱為遞回，（核心就是大事化小）
遞回的倆個必要條件：
*存在限制條件，當滿足這一限制條件時，遞回便不再繼續，
*每次遞回呼叫之后越來越接近這個限制條件，
例題：根據下面遞回函式：呼叫函式Fun(2)，回傳值是多少
int Fun(int n)
{
if(n==5)
return 2;
else
return 2*Fun(n+1);
}
分析：
Fun(2)--->回傳16
return 2*Fun(3) 2*8=16
|__Fun(3):8
return 2*Fun(4) 2*4=8
|__Fun(4):4
return 2*Fun(5) 2*2=4
|__Fun(5):2
return 2
例題：按照時序列印一個數
void print(unsigned int n)//123
{
if (n > 9)
{
print(n / 10);
}
//else 切記這個else不能加，不是非此即彼的關系！！！
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf("%u", &num);//123
//遞回 - 函式自己呼叫自己
print(num);//print函式可以列印引數部分數字的每一位
return 0;
}
決議圖：
決議：
我們以輸入123為例，首先進入到print(123 / 10);再進入print(12/ 10);再進入print(1 / 10);因為1<9，1 % 10=1，所以先輸出1，再往外12% 10=2輸出2，再往外層123% 10=3輸出3，
2.遞回溢位
例題：
void test(int n)
{
if (n < 10000)//深度遞回，容易導致堆疊溢位
{
test(n + 1);
}
}
int main()
{
int a = 10;
test(1);
return 0;
}
深度遞回導致堆疊溢位！！！
3.（多練幾次，重在理解）：撰寫函式不允許創建臨時變數，求字串長度，
#include <string.h>
//1.非遞回解法
int my_strlen(char* str)
{
int count = 0;
while (*str != '\0')
{
count++;
str++;
}
return count;
}
//2.遞回解法
int my_strlen(char* str)//str只是地址，所以還需要*解參考運算子
{
if (*str != '\0')
return 1 + my_strlen(str + 1);
//改成++str或str++都不對，因為遞回傳進去跟留下來的不合要求
else
return 0;
}
int main()
{
char arr[] = "bit";
//['b']['i']['t']['\0']
//
//模擬實作一個strlen函式
printf("%d\n", my_strlen(arr));//陣列名相當于首元素地址
return 0;
}
決議圖：
4.遞回與迭代
例題1：求n的階乘
//1.迭代
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int ret = 1;
for (i = 1; i <= n; i++)
{
ret = ret * i;
}
printf("%d\n", ret);
return 0;
}
//2.遞回
int Fac(int n)
{
if (n <= 1)
return 1;
else
return n * Fac(n - 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
//有一些功能：可以使用迭代的方式實作，也可以使用遞回
例題2：求第n個斐波那契數0、1、1、2、3、5、8、13、21、34
//遞回可以求解，但是效率太低，一直重復計算
//解法1，遞回效率極低
int count = 0;
int Fib(int n)
{
//統計第3個斐波那契數的計算機次數
if (n == 3)
count++;
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
printf("count = %d\n", count);
return 0;
}
//解法2，迭代回圈
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n>2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
5.漢諾塔問題（假設有24個盤子）
除了a最下面的盤子之外，其他的23個都移動到了b上，這時候把最下面的盤子由a移動到c即可，
當最大的盤子由a移動到c，b上是是剩下的23個盤子，a空了，現在的任務是把23個從b轉移到c，
子問題同原問題，只是調整規模24->23，方法類似，先將上面的22個盤子由b移到a，再將最下面的盤子移到c，
…
如此重復遞回直到規模達到預定值，
6.青蛙跳臺階問題（類似斐波那契數列）
當n=3時，青蛙最后一次跳的時候有兩種可能，一種是最后一次跳了1級，一種是最后一次跳了兩級，當n>3時，最后一步跳法同理，
我們將以上思路抽象成數學公式，令f(n)為n級臺階的總跳法數，如果最后一步選擇跳1級的話，之前就只有(n-1)級臺階可跳，(n-1)級的總跳法數是f(n-1)，如果最后一次跳2級的話，之前就只有(n-2)級臺階可跳，(n-2)級臺階的總跳法數是f(n-2)，因為青蛙最后一步不是跳1級就是跳2級，所以剛剛列舉的就是青蛙的所有跳法，即f(n)=f(n-1)+f(n-2).
7.撰寫一個函式 reverse_string(char * string)（遞回實作）
實作：將引數字串中的字符反向排列，不是逆序列印，
**要求：**不能使用C函式庫中的字串操作函式，
/*
非遞回思路：
逆置字串，回圈的方式實作非常簡單
1. 給兩個指標，left放在字串左側，right放在最后一個有效字符位置
2. 交換兩個指標位置上的字符
3. left指標往后走，right指標往前走，只要兩個指標沒有相遇，繼續2，兩個指標相遇后，逆置結束
*/
void reverse_string(char* arr)
{
char *left = arr;
char *right = arr+strlen(arr)-1;
while(left<right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
/*
遞回方式（好好理解）：
對于字串“abcdefg”，遞回實作的大概原理：
1. 交換a和g，
2. 以遞回的方式逆置源字串的剩余部分，剩余部分可以看成一個有效的字串，再以類似的方式逆置
*/
void reverse_string(char* arr)
{
int len = strlen(arr);
char tmp = *arr;
*arr = *(arr+len-1);
*(arr+len-1) = '\0';
if(strlen(arr+1)>=2)
reverse_string(arr+1);
*(arr+len-1) = tmp;
}
8.寫一個遞回函式DigitSum(n)，輸入一個非負整數，回傳組成它的數字之和
例如，呼叫DigitSum(1729)，則應該回傳1+7+2+9，它的和是19
輸入：1729，輸出：19
/*
思路：
n n < 10
DigiSum(n) =
DibiSum(n/10)+n%10 // 前n-1位之和+第N位
*/
int DigitSum(int n)//1729
{
if(n>9)
return DigitSum(n/10)+n%10;
else
return n;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278119.html
標籤：其他