递推和递归

递推

递推犹如斐波那契数列：f(0) = 1, f(1) = 1;

f(n) = f(n-1) + f(n-2);

1 int i = 0;
2 long fib[NUM] = {1,1};
3 f(i=0; i<NUM; i++){
4     fib[i] = fib[i-1] + fib[i-2];
5 }

注意这里只是循环没有自己调用自己。

递归犹如汉诺塔：

当A塔上有两个盘子是，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。

A塔上有三个盘子，B塔会有两个正常的盘子（当然要借助C塔），然后，将最大的盘子移到C塔，然后将盘子移动到C塔上（借助A塔）。

同理A塔上有N个盘子，B塔上有N-1个正常的盘子（借助C塔），然后，将N号盘子移动到C塔，最后将盘子移到C塔（借助A塔）。

赤裸裸的递归,先来介绍一个函数，如下所示。

hanoi(N,from,depend_on,to);//先将初始塔的前n个盘子借助目的塔移动到借用塔上

所以汉诺塔核心代码如下。

 1 hanoi(int n,char from, char depend_on, char to)
 2 {
 3     if(n==1)
 4         printf("%d\t %c->%c",n, from, to);
 5     else
 6         {
 7             hanoi(n-1,from, to, depend_on);//先将初始塔的前n-1个盘子借助目的塔移动到借用塔上 
 8             printf("%d\t %c->%c",n, from, to);//将剩下的一个盘子移动到目的塔上  
 9             hanoi(n-1,denpend_on,from,to);//最后将借用塔上的n-1个盘子移动到目的塔上  
10         }
11 }

自己调用自己了参见第7行和第九行。