递归--例子与简单分析
递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程
------------------维基百科
我记得大学计算机结构与算法的一节课上，老师给我们讲解了递归的整个调用过程，印象还挺深刻的，因为老师说，，。递归，就是有递有归，有个问题，我们解决不了，但是我们可以不断的将问题简化成相同问题的子问题，直到子化成我们可以解决的问题，返回一个解决方法，然后这个解决方法可以解决更大的问题并返回一个解决方法，如此反复，大问题就解决了，其实递归是一种解决问题的手段，而这种思想就是分治思想，对工作中生活中解决问题非常有帮助。
递归一般都有一个递归函数，这个函数直接调用自己或者通过一系列的调用语句间接的调用自己，
而函数里边一般都会有两部分，
- 递归结束条件的语句，边界条件；
- 递归调用自己的语句，简化问题。
如果不理解递归，那这个模版也可以套用吧。不过分治的思想真的很重要，需要掌握。
接下来可以分析一些实际的问题来帮助我们更加理解，先从hello world式的N的阶乘开始
- 计算n!的阶乘，原始的计算机自然一下子当然难以计算，但是我们只要计算出(n-1)!了，n!就能通过(n-1)*n计算出来了呀。那结束条件是n=1的时候，我们让1!=1，这样，当n不断递减，到1的时候，我们就能得到结果了
//计算n!
//构造一个递归函数，两个部分：
//n=1 的时候，返回1，因为1的阶乘就等于1；
//n!=1 的时候，继续调用自己，计算n-1的阶乘，并返回n \* (n-1)!；
int recursion(int n) {
if (n == 1) {
return 1;
}
return recursion(n-1)*n;
}
- POJ 1664 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
这道题类似整数划分问题，整数划分使用了一个相加的个数来辅助递归，这种递归有两种情况：
//n>m,有n-m个盘子是空的，这几个盘子不影响结果, fun(m,n)=fun(m,m)
//n<m,
//1,至少一个盘空着：f(m,n)=f(m,n-1)
//2,所有盘都放了苹果：f(m,n)=f(m-n,n)
//结果= 情况1+情况2..
int fun(int m, int n) {
if(m==0 || n == 1)
return 1;
if(n>m)
return fun(m,m);
else
return fun(m,n-1)+fun(m-n,n);
}
- Hanoi Tower 汉诺塔问题
这个问题应该都很熟悉了,有三个桌子a,b,c, 从a移动n个盘子到c,我们不知道怎么移,但是我们可以把移动n-1个盘子当作一个整体子问题，然后在这个基础上做些移动操作然后完成移动n个盘子的操作。
// 问题hanoi(a,b,c,n)：
// 三个操作：
// 把n-1个盘子从a移动到b; hanoi(a,c,b,n-1)
// 把第n个盘子从a移动到c; move(a,c)
// 把n-1个盘子从b移动到c; hanoi(b,a,c,n-1)
void hanoi(char a, int b, int c, int n) {
if(n == 1)
printf("\n%c->%c\n"a,c);
else {
hanoi(n-1,a,c,b);
printf("\n%c->%c\n"a,c);
hanoi(n-1,b,a,c);
}
}
- 斐波拉契数列求和
//典型的递归问题
int Fibonacci(int n){
if (n <= 1)
return n;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
- 输入字符串，反转输出，类似的还有判断一段字符串回文等
//字符串反转输出，其实是利用了递归的从最里层返回的特性
void recursion() {
char t;
cin >> t;
if (t == '1') {
return;
}
if (t != '1') {
recursion();
printf("%c",t);
}
}
递归的简单分析：递归虽然易读，而且简单，但是他的运行效率较低，时间，空间复杂度都比非递归算法要高。因为递归调用实际上是函数自己在调用自己，而函数的调用开销很大，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。
比如说，求n的阶乘，其实如果使用迭代法来计算的话，他们的时间复杂度都是O(n),但是由于递归会需要多次发生函数调用，所以递归算法来计算的效率还是会低一些的。
