C 遞歸經典實例

1

菲波那切數(shù)列：求第N個數(shù)列的值

#include <stdio.h>
long long Fib(int  n){
    return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
}

int main(){
	 printf("%ld\n",Fib(40));
}

C:\MinGW\project>gcc -std=c99 main.c

C:\MinGW\project>a.exe
102334155

遞歸求出年齡：

每一個人比前面一個人大2歲，最前面那個人是10歲，求第n個人的年齡

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

int main(){
	printf("age = %d",recurse(20));
}

C:\MinGW\project>gcc str.c
C:\MinGW\project>a.exe
age = 48

漢諾塔問題

#include <stdio.h>
long num=0;
void hanoi(int n,char A,char B,char C){//理解為：有n個盤子在A上，通過B，移到C
	if(n==1)
		printf("第%ld步:\t%c -> %c\n",++num,A,C);
	else{
		hanoi(n-1,A,C,B); 
		printf("第%ld步:\t%c -> %c\n",++num,A,C); 
		hanoi(n-1,B,A,C);
	}
}

int main(){
	int n=0;
	printf("請輸入盤子的個數(shù)\n");
	scanf("%d",&n);
	printf("盤子的移動方向如下\n");
    hanoi(n,'A','B','C'); 
}

C:\MinGW\project>gcc  main.c
C:\MinGW\project>a.exe
請輸入盤子的個數(shù)
5
盤子的移動方向如下
第1步:  A -> C
第2步:  A -> B
第3步:  C -> B
第4步:  A -> C
第5步:  B -> A
第6步:  B -> C
第7步:  A -> C
第8步:  A -> B
第9步:  C -> B
第10步: C -> A
第11步: B -> A
第12步: C -> B
第13步: A -> C
第14步: A -> B
第15步: C -> B
第16步: A -> C
第17步: B -> A
第18步: B -> C
第19步: A -> C
第20步: B -> A
第21步: C -> B
第22步: C -> A
第23步: B -> A
第24步: B -> C
第25步: A -> C
第26步: A -> B
第27步: C -> B
第28步: A -> C
第29步: B -> A
第30步: B -> C
第31步: A -> C

求數(shù)的和

chunli@ubuntu:/tmp$ cat sum.c 
#include <stdio.h>

int sum(int n)
{
	if (n ==1)
		return 1;
	else
		return n + sum(n-1);

}




int main()
{

printf("sum =%d \n",sum(10) );

}
chunli@ubuntu:/tmp$ gcc sum.c ;./a.out 
sum =55

求1到n之間質數(shù)的和

#include <stdio.h>

int isprime(int n, int key)//判斷n是否為素數(shù)，是返回1，不是返回0
{
	if (n < 2)
		return 0;
	if (n == key)
		return 1;
	if (n % key == 0)
		return 0;//除了1和他本身以外，有余數(shù)，證明不是素數(shù)，返回假
	else
		return isprime(n, key + 1);
}

int sum(int n)//求1到n之間所有素數(shù)之和
{
	if (n == 1)
		return 1;
	else
	{	
		if (isprime(n, 2))
			return  n + sum(n - 1);//如果n為素數(shù)，遞歸求和
		else
			return sum(n - 1);//如果n不為素數(shù)，只遞歸，不求和
	}
}

int main()
{
printf("1 -- 2 質數(shù)和 %d \n",sum(2));
printf("1 -- 3 質數(shù)和 %d \n",sum(3));
printf("1 -- 10質數(shù)和 %d \n",sum(10));
}






chunli@ubuntu:/tmp$ ./a.out 
1 -- 2 質數(shù)和 3 
1 -- 3 質數(shù)和 6 
1 -- 10質數(shù)和 18