关于递归调用

例如：第一个孩子十岁，第二个孩子比第一个孩子大两岁，第三个孩子比第二个孩子大两岁，第四个孩子比第三个孩子大两岁，第五个孩子比第四个孩子大两岁，求第五个孩子多少岁。

普通算法：

#include <stdio.h>
int Age1(int n)
{
 int tmp = 10;
 for(int i=1;i<n;i++)
 {
  tmp += 2;
 }
 return tmp;
}

递归算法：

Age(5):第五个人的年龄
Age(4):第四个人的年龄
Age(3):第三个人的年龄
Age(2):第二个人的年龄
Age(1):第一个人的年龄
Age(n):第n个人的年龄
Age(n-1):第n-1个人的年龄
int Age(int n)
{
 int tmp;
 if(n == 1)
  tmp = 10;
 else
  tmp = Age(n-1) + 2;
 return tmp;
}

 递归调用过程图：

 菲波那切数列（最不适合运用递归）

普通算法：

int Fibon_for(int n)//O(n),O(1)
{
 int f1 = 1;
 int f2 = 1;
 int f3 = 1;
 for(int i=1;i<n;i++)
 {
  f3 = f1 + f2;
  f1 = f2;
  f2 = f3;
 }
 return f3;
}

int main()
{
 printf("%d\n",Fibon(40));

递归算法：

int Fibon(int n)
{
 if(n==0 || n==1)
 {
  return 1;
 }
 else
 {
  return Fibon(n-1)+Fibon(n-2);
 }
}
 

 

汉诺塔(最适合运用递归）

#include <stdio.h>

int g_count = 0;
void Move(char x,char y)
{
 g_count++;
 printf("%c->%c\n",x,y);
}

void Hanoi(int n,char a,char b,char c)
{
 if(n == 1)
 {
  Move(a,c);
 }
 else
 {
  Hanoi(n-1,a,c,b);
  Move(a,c);
  Hanoi(n-1,b,a,c);
 }
}

int main()
{
 Hanoi(10,'A','B','C');//64
 printf("%d\n",g_count);

 return 0;
}