什么是函式遞回？
程式呼叫自身的編程技巧稱為遞回（ recursion），
遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，
遞回的主要思考方式在于：把大事化小
遞回的兩個必要條件：
1.存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
2.每次遞回呼叫之后越來越接近這個限制條件，
下面來看一下遞回的具體栗子
例1：
接受一個整型值（無符號），按照順序列印它的每一位，
例如：
輸入：1234，輸出 1 2 3 4.
思路：
首先我們可以知道最容易得到的數字為4，1234%10=4，同理123%10=3，而1234/10=123,以此類推，所以我們可以給出一個簡單的演算法:
1234%10=4
1234/10=123 —— 123%10=3
123/10=12 ——12%10=2
12/10=1 ——1%10=1
這樣就能一次求出數字了，
給出代碼：
#include <stdio.h>
void print(int n)
{
if(n>9)
{
print(n/10);
}
printf("%d ", n%10);
}
int main()
{
int num = 1234;
print(num);
return 0;
按如上代碼圖解說明遞回是如何實作的
紅色的箭頭表示在函式內部呼叫函式的程序，藍色的箭頭表示函式呼叫完后回傳的程序，其中，函式體內的判斷陳述句"if(n>9)"即為整個遞回程序中的限制條件，在最后一次呼叫中，我們可以看出，"n/10"的結果明顯不在滿足再次呼叫的條件，所以呼叫結束，函式開始回傳，最終得到想要的結果，
例2：
strlen的模擬（可以用回圈實作，也可以用遞回來實作，這里重點說遞回實作）
strlen的含義是：求字串中有效字符的長度，不包括\0，即計算字符’\0’前的字符個數
回圈實作：
- 給一個計數，用來統計有效字符的個數
- 遍歷字串，只要沒有遇到\0, 遇到一個字符給計數加1，直到遇到\0
#include<stdio.h>
int my_strlen(char* str)
{
int count = 0;
while('\0' != *str)
{
count++;
str++;
}
return count;
}
int main()
{
char arr[]="Hello world";
printf("%d",my_strlen(arr));
return 0;
}
遞回實作：
int my_strlen(char *str)
{
if('\0' == *str)
return 0;
else
return 1+my_strlen(1+str);
}
主函式（略）
每次呼叫一次 my_strlen 函式，回傳值就+1，最后的限制條件為當訪問到’\0’時就退出，
例3：
撰寫一個函式 reverse_string(char * string)（遞回實作）
實作：將引數字串中的字符反向排列，不是逆序列印，
要求：不能使用C函式庫中的字串操作函式，
比如:
char arr[] = “abcdef”; 逆序之后陣列的內容變成：fedcba
同上題，有兩種實作方式（回圈和遞回）這里重點講遞回實作
回圈實作：
思路：
- 給兩個指標，left放在字串左側，right放在最后一個有效字符位置
- 交換兩個指標位置上的字符
- 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”，遞回實作的大概原理：
- 交換a和g
- 以遞回的方式逆置源字串的剩余部分，剩余部分可以看成一個有效的字串，再以類似的方式逆置
void reverse_string(char* arr)
{
int len = strlen(arr);//計算字串的長度
char tmp = *arr;//1.將首字符放入一個臨時變數中
*arr = *(arr+len-1);//2.將最后一個非\0的字符放入第一個字符的位置中
*(arr+len-1) = '\0';//3.將字符'\0'放入最后一個非\0的字符位置中
if(strlen(arr+1)>=2)
reverse_string(arr+1);//4.若剩下的字符個數在2個以上，呼叫該函式
*(arr+len-1) = tmp;//5.將此次的首字符放入上述第3步中放入'\0'字符
// 的位置中
}
主函式（略）
為了理解，畫圖說明：
經過上述5步，就能用遞回的方法實作字串的逆序了，
對遞回方法的總結：
1.不能死遞回，都有跳出條件，每次遞回需逼近跳出條件
2.遞回層次不能太深，避免堆疊溢位
所謂堆疊溢位，作以下說明：
相對其他方法而言，遞回的方法雖然有些時候比較巧妙，但也存在缺陷，遞回所需要的空間相對比較大，運行效率相對低，存在堆疊溢位的問題；所以在用遞回之前需注意這些問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/291240.html
標籤：其他
上一篇：一個故事看懂行程間通信技術