遞回
溫馨提示：函式部分中比較難一塊，需要大量的積累和練習，不懂的地方多除錯，和畫圖，才能有遞回的思想！！！！
博主就是不懂就畫圖，畫完圖就茅塞頓開
文章目錄
- 遞回
- 思維導圖
- 例子思路
- 例子1
- 例子2
- 例子3
- 例子 4
- 例子 5
- 拓展
- 注意事項
- 青蛙跳臺階
- 漢諾塔
思維導圖
看這個思維導圖，我大致說一下他的運用場景，和下面的例子比較好理解
遞回自己直接或間接呼叫自己，把一個大型的問題層層轉換成一個小的問題，需要的代碼也是少之又少，大大減少了代碼量，遞回思想：大事化小，看例子吧，結合例子比較好懂，
例子思路
下面舉的例子沒有提到的思路都在這里
例子1
輸入123列印 1 2 3
思路
- 123中誰最好獲取，當然是3，123%10就獲得3，然后在123/10獲得12在%10以此往復，就可以獲得，那我們來看看代碼吧
void print(int n)
{
if (n >9)
{
print(n / 10);//n大于9就進入遞回，直到n<9是跳出遞回
}
printf("%d ", n % 10);
}
int main()
{
int num = 123;
print(num);
return 0;
}
看他的運行圖比較好理解
函式從哪里進來就要從哪里回傳回去
例子2
n的階乘（迭代）
int Fib(int n)
{
int i = 0;
int fib = 1;
for ( i =1; i <=n; i++)
{
fib = fib * i;
}
return fib;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret =Fib(n);
printf("%d", ret);
return 0;
}
n的階乘（遞回）
int Fib(int n)
{
if (n <2)
{
return 1;
}
else
{
return n*Fib(n - 1) ;
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d", ret);
return 0;
}
- 這里和迭代（回圈）起來遞回更加簡單一個if else就搞定了，用少量代碼就完成了（好方便哈哈）
遞回的流程圖
例子3
模擬實作strlen
- strlen的作用是就求字串長度
- strlen是會記錄\0前面字符個數
strlen（迭代版）
int my_strlen(char* a)//傳過來地址，也用地址接收
{
int count = 0;
while(*a != '\0')
{
a++;
count++;
}
return count;
}
int main()
{
char arr[] = "abcdef";
printf("%d", my_strlen(arr));//陣列的地址就是首元素
return 0;
}
strlen（遞回版）
int my_strlen(char* a)//傳過來地址，也用地址接收
{
if (*a != '\0')
{
return 1 + my_strlen(a + 1);//這里不要用a++或者++a,不然會改變a的值假設這不是陣列是變數
}
else
return 0;
}
int main()
{
char arr[] = "abcdef";
printf("%d", my_strlen(arr));//陣列的地址就是首元素
return 0;
}
流程圖
例子 4
斐波那契數列
規律就是，前面倆數向加得出后面那個數
- 斐波那契就是n=（n-1）+（n-2）
遞回版
int Fib(int n)
{
if (n <= 2)//斐波那契數列前倆位是1 1
{
return 1;
}
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d",Fib(n));
return 0;
}
看一下流程圖
迭代版
int Fib(n)
{
int a = 1;
int b = 1;
int c = 1;
if (n <= 2)
{
return c;//斐波那契前面倆數是
}
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", Fib(n));
return 0;
}
- 這里看起來比起來還是比遞回麻煩呀，又是判斷，又是回圈，又是交換，麻煩死了還不如寫遞回呢，直接一個判斷，寫個一個條件就開始遞回多方便，不不不，那我們看一下下面的例子，求第50個斐波那契數的時間
是不是以為程式掛了，不不不，其實計算機在很努力的在算，不信我給你看
騙你是小狗
………………………………喝了一杯水，還沒好，又是一杯，還沒好，煎熬
………………………………，哦出來了花了6分43秒
為啥遞回要花怎么長時間呢，應為他的效率低
因為他假設要找第50，他就要找的第49 和48然后就要，然后找49就要找到48和47………………，找一位數就進行了多次重復大量的計算，算出這個數大致算了2^n-1次方
- 這里迭代就很快，ctrl+f5除錯，直接給出答案
例子 5
- 字串逆序
- 字符陣列中“abcdef”,交換位置,“fedcba”
思路
1:加換a和f，在b和e,這個不是和二分查找原因二分查找思想 二分查找的思路
迭代版 1
#include<string.h>
void reverse_string(char* a,int s)//傳過來是地址就用地址接收
{
int left = 0;
int right = s - 1;
while(left<right)
{
char cmp = *(a + left);//=str[left]
*(a + left) = *(a + right);
*(a + right) = cmp;
left++;
right--;
}
}
int main()
{
char arr[] = "abcdef";
int st = strlen(arr);
reverse_string(arr,st);//陣列的地址就是首元素
printf("%s", arr);
return 0;
}
迭代版 2
#include<string.h>
void reverse_string(char* a, int s)//傳過來是地址就用地址接收
{
int left = 0;
int right = s - 1;
while (left < right)
{
char cmp = a[left];//=str[left]
a[left] = a[right];
a[right] = cmp;
left++;
right--;
}
}
int main()
{
char arr[] = "abcdef";
int st = strlen(arr);
reverse_string(arr, st);//陣列的地址就是首元素
printf("%s", arr);
return 0;
}
遞回版
這里想到遞回的思路很難，誰能想到，吧后面給換成\0,然后在字串長度對比天吶！！
void reverse_strling(char* str)
{
char tmp = *str;
int len = strlen(str);
*str = *(str + len - 1);
*(str + len - 1) = '\0';
if (strlen(str + 1) >= 2)
{
reverse_strling(str + 1);
}
*(str + len - 1) = tmp;
}
int main()
{
char arr[] = "abcdef";
reverse_strling(arr);//陣列的地址就是首元素
printf("%s", arr);
return 0;
}
流程圖
這里總結得出，遞回與跌代，不向上下，各有各的好處，作為裁判的我（公平公正）平局
拓展
堆疊（現在所認識到的）
- 函式在自己呼叫自己的時候會在堆疊區中創建一塊新的空間，堆疊溢位就是把堆疊撐滿了
這個就是記憶體情況
注意事項
- 寫遞回的時候一定要有判斷條件，和逼近跳出遞回的條件
- 遞回不要太深，太深容易堆疊溢位（strank）
- 如果遞回效率慢，那么就不適合遞回，那就一定要寫出迭代方法（不管多麻煩），遞回的目的是大事化小，如果效率慢，豈不是本末倒置了
- 創建函式的時，取名字最好和他的功能對應，不要隨便取
青蛙跳臺階
正常跳臺階：一只青蛙一次可以跳上1級臺階，也可以跳上2級，也可以跳上3級，
求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果），
- 設跳1級---->跳法1------->[1]
- 跳2級----->跳法2----->[1,1],[2]
- 跳3級---->跳法3----->[1,1,1],[2,1],[1,2],
- 跳4級----->跳法5---->[1,1,1,1],[2,2],[1,1,2,2],[2,2,1,1] [1,2,1]
- 跳5級----->跳法8---->[1,1,1,1,1],[2,2,1],[1,2,2],[2,1,2,],[[2,1,1,1,1],[1,2,1,1],[1,1,2,1,1]，[1,1,1,2],
不能說一樣，就是一毛一樣
漢諾塔
漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，
A=1,2,3. B =0. C= 0
- A(1)–>C
- A(2)—>B
- C(1)---->B(2)
- A(3)---->C
- B(1)---->A
- B(2)—>C(3)
- A(1)---->C(2)
青蛙跳臺階和漢諾塔，會在下期更新…………
（如果有錯誤記得聯系博主（QQ：1696912943），或者直接在評論區提出，私信，博主會及時進行改正，謝謝）
持續更新中………………
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279254.html
標籤：其他