C語言詳解：函式遞回專題

函式遞回

函式遞回的定義和優缺點

程式呼叫自身的行為就是遞回，可以直接或間接的呼叫，本質是把復雜的問題轉化為一個規模小的問題，遞回一般只需少量的代碼就可描繪出多次重復計算，其主要思考方式在于大事化小，

優點是為具有某些特征的編程問題提供了最簡單的策略，缺點是層層呼叫，演算法的復雜度可能過高，以致于快速耗干了計算機的記憶體資源，不方便閱讀和維護等，

遞回的使用場景及必要條件

使用場景

1. 能夠要求轉化為新的問題，且二者解決方法相同，所處理的物件存在規律變化，
2. 非遞回比較麻煩，而遞回很簡單，
3. 有模板或是公式可以直接套用，不會出現明顯問題，

必要條件

• 明確存在限制條件
• 每次遞回越來越逼近條件

遞回的細節說明

• 每級遞回都有自己的變數，可能名稱相同，但是其值不同，

  遞回呼叫時，系統自動保留當前函式的引數變數，每次呼叫系統都會為函式開辟相應的空間，

• 每次呼叫都要回傳值，遞回執行結束后，控制權傳回到上一級函式，

  呼叫結束后，系統釋放本次呼叫所開辟的空間，程式回傳到上一次的呼叫點，同時獲得初進該級呼叫的引數，

  每級遞回必須逐級回傳，不可跳躍或間斷，

• 函式中遞回陳述句之前的代碼，按被調函式的順序執行，遞回之后的代碼，與被調函式相反的順序執行，

遞回的習題講解

1列印整數每一位

用遞回的方式，實作列印一個整數的每一位的功能，

輸入輸出示例

輸入：1234

輸出：1 2 3 4

解題思路

print(1234)
= = = print(123)+4
= = = print(12)+3+4
= = = print(1)+2+3+4
= = = printf(1)+2+3+4

這便是前面使用場景中所寫的，將題目要求問題轉化為新的問題，且變數有規律的變化

代碼邏輯

n是不是個位數，遞推呼叫n / 10

n是個位數，回歸列印n % 10

void Print(int n) 
{
	if (n > 9)
	{
		Print(n / 10);
	}
	printf("%d ", n%10);
}
int main()
{
	int num = 0;
	scanf("%d", &num);
	Print(num);	
	return 0;
}

2遞回和非遞回求n階乘

用遞回和非遞回的方法，分別實作求n的階乘的功能（不考慮溢位），

輸入輸出示例

輸入：5

輸出：120

解題思路

n ? n ? 1 ? n ? 2 ? n ? 3 ? … ? 1 n*n-1*n-2*n-3*…*1 n?n?1?n?2?n?3?…?1

代碼邏輯

f a c ( n ) = n ? f a c ( n ? 1 ) , n > 0 fac(n) = n * fac(n-1) , n>0 fac(n)=n?fac(n?1),n>0

f a c ( n ) = 1 , n = 0 fac(n) = 1 , n=0 fac(n)=1,n=0

int fac(int n)//非遞回
{
	int ret = 1;
	for (int i = 1; i <= n; i++)
	{
		ret *= i;
	}
	return ret;
}
int fac(int n)//遞回
{
	if (n > 0)
		return n * fac2(n - 1);
	else
		return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);	
	printf("%d\n", fac(n));
	return 0;
}

3strlen函式模擬

輸入輸出示例

輸入：abcdef

輸出：6

解題思路

strlen(abcdef\0)
1+strlen(bcdef\0)
1+1+strlen(cdef\0)
1+1+1+strlen(def\0)
1+1+1+1+strlen(ef\0)
1+1+1+1+1+strlen(f\0)
1+1+1+1+1+1+strlen(\0)

代碼邏輯

若 ? c h ≠ 0 , s t r l e n ( a r r ) = 1 + s t r l e n ( a r r + 1 ) 若 *ch≠0 , strlen(arr) = 1 + strlen(arr+1) 若?ch?=0,strlen(arr)=1+strlen(arr+1)
若 ? c h = 0 , s t r l e n ( a r r ) = 0 若*ch=0 , strlen(arr) = 0 若?ch=0,strlen(arr)=0

int my_strlen(char* ch)
{
	if (*ch != '\0')
	{
		return 1 + my_strlen(ch + 1);
	}
	return 0;
}
int main()
{
	char ch[20] = { 0 };
	scanf("%s", &ch);
	printf("%d", my_strlen(ch));
	return 0;
}

4逆序字串

不開辟額外空間的情況下，不使用字串庫函式，遞回實作字串反向排列，而不是倒序列印，

輸入輸出示例

輸入：abcdef

輸出：fedcba

解題思路

abcdef

遞推：（先把后面賦值給前面，后面用覆寫\0）

$ \Rightarrow$ f b c d e \0

? \Rightarrow ? f e c \0\0

? \Rightarrow ? f e d \0\0\0

回歸：（把前面轉移出去的字符對應賦值給\0）

$ \Rightarrow$ f e d c \0\0

? \Rightarrow ? f e d c b \0

? \Rightarrow ? f e d c b a

代碼邏輯

reverse("abcdef\0") 交換a和f+reverse("f bcde\0\0") 交換a和f+交換b和e+reverse("fe cd\0\0\0") 交換a和f+交換b和e+交換c和d+reverse("fed \0\0\0\0")

• 交換兩個字符
  1. 將在前的字符先放到一邊存著
  2. 把在后的字符賦值到前面的位置
  3. 再把后面的位置對應覆寫為\0
• 原在前字符替換\0
  1. 把事先存好的在前的字符對應替換到\0的位置上

void reserve_string1(char* ch)//指標
{
	char* left = ch;
	char* right = ch + strlen(ch) - 1;
	while (left < right)
	{
		char tmp = *left;//不能交換地址，只能交換內容
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
void reserve_string2(char* ch)//陣列
{
	int left = 0;
	int right = strlen(ch) - 1;
	while (left < right)
	{
		char tmp = ch[right];
		ch[right] = ch[left];
		ch[left] = tmp;
		left++;
		right--;
	}
}

void reverse_string3(char* ch)//遞回
{
	char* left = ch;
	char* right = ch + strlen(ch) - 1;

	if (*ch != '\0')
	{
		char tmp = *left;//提取
		*left = *right;//賦值
		*right = '\0';//賦\0

		reverse_string3(ch+1);//ch+1,而不是ch++

		*right = tmp;//賦值
	}
}
int main()
{
	char ch[20] = "abcdef";
	//char* ch = "abcdef";//err - 常量字串不可修改
	reverse_string3(ch);
	printf("%s\n", ch);

	return 0;
}

5遞回實作數字各位之和

寫一個遞回函式DigitSum()，輸入一個非負整數，回傳組成它的數字之和

輸入輸出示例

輸入：1234

輸出：10

解題思路

1234
DigitSum(123)+4
DigitSum(12)+3+4
DigitSum(1)+2+3+4

1+2+3+4

1234%10=4
1234/10=123

123%10=3
123/10=12

12%10=2
12/10=1

1%10=1
1/10=0

一個數模10得到尾數，除10得到尾數前面的數字

通過不斷的除10模10，就可以把每一位數字放到末尾，從而得到每一位數字

代碼邏輯

若n不為個位數，先%10得到尾數，再/10

一定要有遞回的出口，即當n為個位數時，函式回傳n

int DigitSum(int n)
{
	if (n > 9)
		return DigitSum(n / 10) + n % 10;
	else
		return n;//遞回的出口
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", DigitSum(n));

	return 0;
}

6求n的k次冪

輸入兩個整數分別代表底數和次冪，遞回實作n的k次冪的功能，

輸入輸出示例

輸入：2 3

輸出：8

解題思路

當k>0時，函式回傳n*power(n,k-1)

當k=0時，函式回傳1，這是程式的出口，是程式遞回到最后必須要計算的值

代碼邏輯

n k = n ? n k ? 1 , k > 0 n^k = n * n^{k-1} ,k > 0 nk=n?nk?1,k>0
n k = 1 , k = 0 n^k = 1 , k = 0 nk=1,k=0

double power(int n,int k)
{
	if (k > 0)
		return n * power(n, k - 1);
	else if (k == 0)
		return 1.0;//遞回的出口k=0
	else
		return 1.0 / power(n, -k);
}
int main()
{
	int n = 0;
	int k = 0;
	scanf("%d%d", &n, &k);
	printf("%lf\n", power(n, k));
    return 0;
}

7遞回求斐波那契數列

遞回和非遞回分別實作求第n個斐波那契數

輸入輸出示例

輸入：5

輸出：5

解題思路

1 1 2 3 5 8 13 21 34 55 89 . . . 1\quad 1\quad 2\quad 3\quad 5\quad 8\quad 13\quad 21\quad 34\quad 55\quad 89\quad ... 1123581321345589...

代碼邏輯

遞回：

F i b ( n ) = F i b ( n ? 1 ) + F i b ( n ? 2 ) , n > 2 Fib(n) = Fib(n-1) + Fib(n-2) , n>2 Fib(n)=Fib(n?1)+Fib(n?2),n>2
F i b ( 1 ) = F i b ( 2 ) = 1 Fib(1) = Fib(2) = 1 Fib(1)=Fib(2)=1

非遞回：

上一次的b換成這一次的a

上一次的c換成這一次的b

如此回圈，就可以從前往后一個一個求，

int Fib(int n)
{
	if (n > 2)
		return Fib(n - 1) + Fib(n - 2);
	else
		return 1;
}

但是這個方法效率是非常低的，當數字特別大時，層層拆分下來，時間效率是 O ( 2 n ) O(2^n) O(2n)，

根據公式可知，第三個斐波那契數可由前兩個得到，我們利用這個規律

int Fib(int n)
{
	if (n <= 2)
		return 1;
	int a = 1;
	int b = 1;
	int c = 1;//n=3時不用運算
	while (n >= 3)//從頭開始移動n-2次，n=3時不用
	{
        c = a + b;
		a = b;//b賦值給a
		b = c;//c賦值給b		
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d",Fib(n));
    
	return 0;
}

經典問題

漢諾塔問題

漢諾塔，小時候游戲機上經常看別人玩的，自己玩到三四局就玩不下去了的那款游戲，當然如果你覺得非常簡單，小時候能玩的行云流水，那你有本事到我面前說，禮貌謝謝（狗頭保命），

游戲規則

有三根柱子，分別為A、B、C ，A柱上從上到下依次排列著由小到大的圓盤，我們需要把圓盤從A柱按照同樣的擺放順序放到C柱上，期間我們可以借助B柱，

• 每次只能挪動一個且是最上面的圓盤
• 按照從上到下依次是由小到大的順序擺放，

解題思路

假設由N個盤子，只需要考慮第 N N N個盤子和其上 N ? 1 N-1 N?1個盤子的整體，顯然思路就是，第 N N N個是要放在 C C C柱上的，

1. 首先將 N ? 1 N-1 N?1個整體是先放在 B B B柱上；
2. 其次將第 N N N個放在 C C C柱上；
3. 最后將 N ? 1 N-1 N?1個整體放到 C C C柱上，

即：第 N N N個 A → B A\rightarrow B A→B， N ? 1 N-1 N?1個整體 A → B → C A\rightarrow B\rightarrow C A→B→C ，然后再考慮 N ? 1 N-1 N?1個中把第 N ? 1 N-1 N?1個當作最后一個，其上 N ? 2 N-2 N?2個當作整體，到最后只剩一個直接放到 C C C柱上，這便是遞回的整體思路，

void move(int n, int x, int z)
{
	printf("%d盤：%c->%c\n", n, x, z);
}
void hannoi(int n, char x, char y, char z)
{
	if (n == 1)
		move(n, x, z);
	else
	{
		hannoi(n - 1, x, z, y);
		move(n, x, z);
		hannoi(n - 1, y, x, z);
	}
}
int main()
{
	int input = 0;
	do 
	{
		printf("輸入盤數開始測驗（0. 退出測驗）\n");
		scanf("%d", &input);
		switch (input)
		{
		case 0:
			break;
		default:
			hannoi(input, 'A', 'B', 'C');
			break;
		}
	} while (input);
	return 0;
}

青蛙跳臺階

游戲規則

? 初階版本

? 青蛙一次可以跳一級臺階，也可以跳兩級臺階，求該青蛙跳n級臺階共有多少種跳法？

? 進階版本

? 青蛙一次可以跳一級臺階，也可以跳兩級臺階，……，也可以跳n級臺階，求該青蛙跳上n級臺階的跳法種數，

解題思路

我們反向思考，當青蛙跳到最高階 N N N階時，他是怎么跳到第 N N N階的呢？

有兩種情況，

• 從第 N ? 1 N-1 N?1階，跳到第 N N N階，最后一次跳一階，
• 從第 N ? 2 N-2 N?2階，跳到第 N N N階，最后一次跳兩階，

圖中用灰框框出的部分，是最后一次跳一階的，其余的是最后一次跳兩階的，

很顯然，除了這兩種情況，別無他法，所以計算青蛙

跳到 N N N階的方法數 = = = 跳 N ? 1 N-1 N?1階的方法數 + + + 跳 N ? 2 N-2 N?2 階的方法數，

同樣，圖中用灰框框出的部分，也代表的是跳 N ? 1 N-1 N?1階的方法數，其余的是跳 N ? 2 N-2 N?2 階的方法數，

這其實就是斐波那契數列，

int fib(int n)
{
	if (n > 1)
		return fib(n - 1) + fib(n - 2);
	else
		return 1;
}