前言

本文總結了幾個遞回基礎例題，c語言實作

遞回的概念

C語言允許函式呼叫它自己，這種呼叫程序叫做遞回(recursion)

遞回的兩個必要條件

1. 存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續
2. 每次遞回呼叫之后越來越接近這個限制條件

例題

1.遞回實作階乘

#include<stdio.h>
int Fac(int n)
{
	if(n<=1)
		return 1;
	else
		return n*Fac(n-1);
}

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

2.遞回實作strlen函式

#include<stdio.h>
int Strlen(const char* str)
{
	if('\0'==*str)
		return 0;
	else
		return 1+Strlen(str+1);
}

int main()
{
	char arr[20]="Hello world!";
	int ret=Strlen(arr);
	printf("%d\n",ret);
	
	return 0;
}

3.計算一個正整數各位數字的和

#include<stdio.h>
unsigned fun(unsigned n)
{
	if(n>9)
		return n%10+fun(n/10);
	else
		return n;
}

int main()
{
	unsigned a=0;
	scanf("%d",&a);
	printf("%d\n",fun(a));
	
	return 0;
}

4.遞回實作整數n的整數k次方

#include<stdio.h>
int fun(int n,int k)
{
	if(0==k)
		return 1;
	else
		return fun(n,k-1);
}

int main()
{
	int n;
	int k;
	scanf("%d %d",&n,&k);
	printf("%d\n",fun(n,k));

	return 0;
}

5.遞回實作斐波那契數

#include<stdio.h>
int Fib(int n)
{
	if(n<=2)
		return 1;
	else
		return Fib(n-1)+Fib(n-2);
}

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

6.遞回實作字串逆序

#include<stdio.h>
#include<string.h>
void reverse_string(char* str)
{
	int len=strlen(str);
	char tmp=*str;
	*str=*(str+len-1);

	*(str+len-1)='\0';
	if(strlen(str+1)>=2)
		reverse_string(str+1);
	*(str+len-1)=tmp;
}

int main()
{
	char arr[20]="hello world!";
	printf("%s\n",arr);
	reverse_string(arr);
	printf("%s\n",arr);

	return 0;
}

注意，前面6次函式呼叫都沒有執行完該次呼叫，只執行到了上圖箭頭所指處，而在第6次呼叫時，if條件不滿足，執行陳述句

*(str+len-1)=tmp;

每一級呼叫執行完該陳述句便回傳上一級呼叫，字符陣列里的內容依次變為

7.漢諾塔

問題描述：
三根柱子A,B,C，最初一摞盤子下大上小的放在A柱子上，現要將盤子移動到C柱子上，要求：

• 一次只能移動一個盤子
• 大盤子不能放在小盤子上

請給出一個可行的方案（每一步怎么移動）

#include<stdio.h>
int count = 1;
void hanoi(int n, char a, char b, char c)//n個盤子從a借助b到c
{
	if (0 == n)
		return;
	hanoi(n - 1, a, c, b);
	printf("step %d: move %d from %c to %c\n", count++, n, a, c);
	hanoi(n - 1, b, a, c);//n-1個盤子從b借助a到c
}

int main()
{
	int n;
	while (scanf("%d", &n))
	{
		hanoi(n, 'A', 'B', 'C');
	}
	return 0;
}

思路
為方便描述，盤子由小到大依次叫做1，2……，n
下面先用N=3的情形下給出一個解法，以得到一個直觀的印象

第一步：
先把1移到C

第二步：
再把2移到B

第三步：
把1移回B

第四步：
把3移到C

第五步：
把1移到A

第六步：
把2移到C

第七步：
把1移到C，就完成了

以上的做法其實是遵循以下規則移動的：
對于有n個盤子

1. 將n-1個盤子由A（借助C）移動到B
2. 將第n個盤子由A移動到C
3. 將n-1個盤子由B（借助A）移動到C
   以上三步便是漢諾塔問題的迭代公式，接下來只要考慮如何實作第一和第三步即可

那么如何將n-1個盤子由A（借助C）移動到B呢？

1. 將n-2個盤子由A（借助B）移動到C
2. 將第n-1個盤子由A移到B
3. 將n-2個盤子由C（借助A）移動到B

那么如何將n-1個盤子由B（借助A）移動到C呢？

1. 將n-2個盤子由B（借助C）移動到A
2. 將第n-1個盤子由B移到C
3. 將n-2個盤子由A（借助B）移到C

8.青蛙跳臺階

問題描述：
一只青蛙一次可以跳一級臺階或跳兩級臺階（不能往回跳），問要跳上n級臺階有幾種跳法

#include<stdio.h>

int frog(int n)
{
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	return frog(n - 1) + frog(n - 2);
}
int main()
{
	int n;
	scanf("%d", &n);
	int ways = frog(n);
	printf("%d\n", ways);

	return 0;
}

思路：
當N=1時，一種方法；
當N=2時，一次跳兩級或兩次跳一級，兩種方法；
當N=3時，若先跳一級，則接下來的方法數即n=2時的方法數；若先跳兩級，則接下來的方法數為n=1的方法數，根據加法原理，n=3的方法數為n=2的方法數+n=1的方法數
以此類推，N=n時的方法數為N=n-1的方法數加上N=n-2的方法數

本質上，這是和斐波那契數相同的問題

9.將一個十進制數以二進制的形式列印

void to_binary(int n);

int main()
{
	int number;
	scanf("%d", &number);
	to_binary(number);

	return 0;
}

void to_binary(int n)
{
	if (n >= 2)
		to_binary(n / 2);
	printf("%d", n%2);

	return;
}

從本題可以看出，遞回在處理倒序問題時非常方便，
對于一個十進制數字，對2求模得到的結果實際上是待輸出二進制數的最后一位，這一規律提示我們在遞回函式的呼叫之前計算n%2，在遞回呼叫之后列印計算結果，這樣計算的第一個值正好是最后一個列印的值，