一、累加—递归

一、代码

二、测试结果

二、汉罗塔问题

一、分析

二、代码

三、测试结果

三、总结

一、累加—递归

一、代码

//累加的递归实现
#include <stdio.h>int addTo(int n)
{if(n <= 0)return 0;else{return addTo(n-1)+n;}
}
void addToTest()
{int n,sum;printf("----addToTest begins.----\r\n");n = 5;sum = addTo(n);printf("\r\r\n0 adds to %d gets %d.\r\n", n, sum);n = 1;sum = addTo(n);printf("\r\r\n0 adds to %d gets %d.\r\n", n, sum);n = -1;sum = addTo(n);printf("\r\r\n0 adds to %d gets %d.\r\n", n, sum);	
}
void main()
{addToTest(); 
} 

二、测试结果

 

时间复杂度和空间复杂度都为O（n) 

二、汉罗塔问题

一、分析

1，先把n-1个圆盘从A借助C成功的移动到B
2，然后再把第n个圆盘从A移动到C
3，最后再把n-1个圆盘从B借助A成功的移动到C

第一步： 

第二步 

第三步

在我们写递归的时候应该先写出终止条件，然后再写递归的逻辑调用，还有一点非常重要，就是一定要明白递归函数中每个参数的含义。 

二、代码

             A为source ,B为transit,C为destination

#include <stdio.h>void hanoi(int n,char source,char transit,char destination)
{if(n <= 0)return ;else if(n==1){printf("%c----->%c\n",source,destination);return ;}else{hanoi(n-1,source,destination,transit);printf("%c----->%c\n",source,destination);hanoi(n-1,transit,source,destination);}	
} 
void hanoiTest() {printf("---- addToTest begins. ----\r\n");printf("2 plates\r\n");hanoi(2, 'A', 'B', 'C');printf("3 plates\r\n");hanoi(3, 'A', 'B', 'C');printf("---- addToTest ends. ----\r\n");
}
void main() 
{hanoiTest();
}

三、测试结果

时间复杂度为O（2^n),空间复杂度为O（n). 

三、总结 

1.递归的调用过程
       每递归调用一次方法，都会在内存中分配空间
       每执行完一次方法，都会释放相应的空间

2.递归必须具备两个条件，一个是调用自己，一个是有终止条件，这两个条件必须同时具备，且一个都不能少，并且终止条件必须是在递归最开始的地方。