C 递归经典实例

1

菲波那切数列：求第N个数列的值

#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("请输入盘子的个数\n");
	scanf("%d",&n);
	printf("盘子的移动方向如下\n");
    hanoi(n,'A','B','C'); 
}

C:\MinGW\project>gcc  main.c
C:\MinGW\project>a.exe
请输入盘子的个数
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

求数的和

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之间质数的和

#include <stdio.h>

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

int sum(int n)//求1到n之间所有素数之和
{
	if (n == 1)
		return 1;
	else
	{	
		if (isprime(n, 2))
			return  n + sum(n - 1);//如果n为素数，递归求和
		else
			return sum(n - 1);//如果n不为素数，只递归，不求和
	}
}

int main()
{
printf("1 -- 2 质数和 %d \n",sum(2));
printf("1 -- 3 质数和 %d \n",sum(3));
printf("1 -- 10质数和 %d \n",sum(10));
}






chunli@ubuntu:/tmp$ ./a.out 
1 -- 2 质数和 3 
1 -- 3 质数和 6 
1 -- 10质数和 18