文章目錄
- 遞回的定義和必要條件
- 初步了解
- 列印一個數的每一位
- 計算一個數的每位之和
- 計算一個數的階乘
- 進階探討
- 二分查找法遞回實作
- 遞回實作字串函式strlen
- 遞回實作字串逆序
- 總結
遞回的定義和必要條件
很多人提到遞回就不由自主的想到了“套娃“二字，確實遞回要函式一層一層地開辟，是非常繞的，那么想要領悟到遞回的精髓我們就要先了解遞回的定義和遞回的必要條件，
定義：
程式呼叫自身的編程技巧稱為遞回（ recursion）， 遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量， 遞回的主要思考方式在于：把大事化小
必要條件：
1、存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
2、每次遞回呼叫之后越來越接近這個限制條件，
當我們理解遞回存在的必要條件后，我們要開始實戰了，通過具體的問題來使用遞回來解決，這樣才能快速掌握，畢竟實踐是檢驗真理的唯一標準，
初步了解
列印一個數的每一位
遞回方式實作列印一個整數的每一位，如1357，我們要列印出1 3 5 7這四個數，
我們就可以想到用取余和取模來分開數字，
1357 % 10 - - - - - - -7 得到數字7
1357 / 1 - - - - - - -135
135 % 10 - - - - - - 5 得到數字5
135 / 10 - - - - - - -13
13 % 10 - - - - - - - 3 得到數字3
13 / 10 - - - - - - - -1
1 % 10 - - - - - - - -1 得到數字1
代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void print(int sum)
{
if (sum >= 10)
{
print(sum / 10);
}
printf("%d ", sum % 10);
}
int main()
{
int sum = 0;
printf("請輸入一個數字：");
scanf("%d",&sum);
print(sum);
printf("\n");
return 0;
}
可能一些朋友看到這里還是有點不太理解，我畫了函式遞回開辟的形象圖有助于理解，圖片如下：
上面的分析我們用到了遞回的定義和必要條件，即遞回存在限制條件，如我們的
if（sum>=10）在這個范圍內就一直開辟函式遞回，等不滿足限制條件后再一層層地回傳去，
運行結果如下：
計算一個數的每位之和
遞回方式實作計算一個數的每位之和，如1234，計算出1+2+3+4=10，如2468，要計算出2+4+6+8=20，
這個和我們上面的列印一個數的每一位是類似的，異曲同工，我們也用取余和取模從而得到1 2 3 4這四個數字，我們先得到4，接著是3，然后再是2，最后數字1不滿足限制條件就一層層回傳直到結束，
代碼如下：
#include <stdio.h>
int fun(int sum)
{
if (sum >= 10)
{
return sum % 10 + fun(sum / 10);
}
else
{
return sum;
}
}
int main()
{
int sum = 0;
printf("請輸入一個數字：");
scanf("%d",&sum);
printf("%d ", fun(sum));
return 0;
}
函式遞回開辟流程圖如下：
程式運行結果：
計算一個數的階乘
比如要計算5的階乘，那就是5 * 4 * 3 * 2 * 1=120，
所以我們闊以大事化小，先得到數字5，然后是4，接著是3，再接著是2，最后是1，所以可以用遞回來實作，我們只要把握住開辟下一個函式時傳過去的數字自減1即可，
代碼如下：
#include <stdio.h>
int fun(unsigned int sum)
{
if (sum > 1)
{
return sum * fun(sum - 1);
}
else
{
return 1;
}
}
int main()
{
unsigned int sum = 0;
printf("請輸入一個數字：");
scanf("%d",&sum);
printf("階乘為：%ld ", fun(sum));
return 0;
}
函式遞回開辟流程圖如下：
上面就是函式遞回的真面目，遞回是自己呼叫自己，但不是停留在一個函式上，而是一直開辟相同的函式，直到不能滿足限制條件，
進階探討
二分查找法遞回實作
二分查找法也被稱為折半法，主要不斷縮小半個區域，一直找下去，
如在 1 2 3 4 5 6 7 8 9 10中找數字7，
發現7比5大，查找空間變為：6 7 8 9 10；
發現7比8小，查找空間變為：6 7 ；
發現7比6大，查找空間變為：7 ；
最后發現就是7，則找到了，
所以思路就明白了，遞回和非遞回寫法如下：
遞回法：
#include <stdio.h>
//不帶回傳值寫法
void fun1(int* p, int left, int right,int k)
{
if (left <= right)
{
int mid = (left + right) / 2;
if (k < p[mid])
{
right = mid - 1;
fun(p, left, right, k);
}
else if (k > p[mid])
{
left = mid + 1;
fun(p, left, right, k);
}
else
{
printf("找到了，下標是：%d\n",mid);
}
}
else
{
printf("找不到\n");
}
}
//帶有回傳值寫法
int fun(int* p, int left, int right, int k)
{
if (left <= right)
{
int mid = (left + right) / 2;
if (k < p[mid])
{
right = mid - 1;
return fun(p, left, right, k);
}
else if (k > p[mid])
{
left = mid + 1;
return fun(p, left, right, k);
}
else
{
return 1;
}
}
else
{
return 0;
}
}
int main()
{
int arr[10] = { 98,0,1,2,3,4,5,6,7,8};
int k = 5;
int left = 0;
//把最后一個元素下標賦值給right
int right = sizeof(arr) / sizeof(arr[0]) - 1;
int ret = Binary_Search(arr, left, right, k);
if (ret!=0)
{
printf("找到了\n");
}
else
{
printf("找不到\n");
}
return 0;
}
非遞回法：
// *****二分查找
#include <stdio.h>
int main()
{
int k = 88; //定義要找的數字
int arr[] = { 11,22,33,44,55,66,77,88,99,100};
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] > k)
{
right = mid - 1;
}
else if (arr[mid] < k)
{
left = mid + 1;
}
else
{
printf("找到了，下標為：%d \n",mid);
break;
}
}
if (right < left)
{
printf("找不到數字\n");
}
return 0;
}
遞回實作字串函式strlen
我們平常求字串長度的時候，用的庫函式就是strlen(),那我們也模擬實作一下，
代碼如下：
#include <stdio.h>
// 迭代方式
int my_strlen1(char* p)
{
int count = 0;
while (*p != '\0')
{
count++;
p++;
}
return count;
}
// 遞回方式
int my_strlen2(char* p)
{
if (*p != '\0')
{
return 1 + my_strlen2(p + 1);
}
else
{
return 0;
}
}
int main()
{
char* p = "abcdefg";
int ret1 = my_strlen1(p);
int ret2 = my_strlen2(p);
printf("遞回方式結果: %d \n",ret1);
printf("迭代方式結果: %d \n", ret2);
}
有興趣的朋友也可以畫一下遞回函式的圖片來分析分析，我這里就不放了哈，
程式執行結果：
遞回實作字串逆序
字串逆序顧名思義就是把字串給顛倒過來，比如 “abcdef” 變成 “fedcba” ，
我們設兩個變數，最左邊為 left ，右邊為 right ，只要把左邊和右邊互換就可以了，
然后 左邊往右邊移動 ，右邊往左邊移動 直到變數 left大于 right ，
所以思路分析完畢，字串逆序也是能夠很好體現遞回的例子，也是利用大事化小，
代碼如下：
#include <stdio.h>
int my_strlen(char* p)
{
if (*p != '\0')
{
return 1 + my_strlen(p + 1);
}
else
{
return 0;
}
}
// 遞回方式寫法
int Reverse(char* p, int left, int right)
{
if (left > right)
{
return 0;
}
else
{
char tmp = p[left];
p[left] = p[right];
p[right] = tmp;
return Reverse(p, left + 1, right - 1);
}
}
//非遞回寫法
void Reverse2(char* p, int left, int right)
{
while (left < right)
{
char tmp = p[left];
p[left] = p[right];
p[right] = tmp;
left++;
right--;
}
}
int main()
{
char arr[] = "abcdef";
int len = my_strlen(arr);
int left = 0;
int right = len - 1;
Reverse(arr,left,right);
printf("反轉結果為：\n");
printf("%s",arr);
printf("\n\n");
return 0;
}
程式執行結果為：
總結
- 許多問題是以遞回的形式進行解釋的，這只是因為它比非遞回的形式更為清晰，
- 但是這些問題的迭代實作往往比遞回實作效率更高，雖然代碼的可讀性稍微差些，
- 當一個問題相當復雜，難以用迭代實作時，此時遞回實作的簡潔性便可以補償它所帶來的運行時開銷，
歡迎大家在評論區留言和探討，大家一起進步，順便點個贊唄！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/291078.html
標籤：其他