/*刚学编程不久，对于递归不太熟悉，于是今天干脆仔细看看递归这一块~*/
/*下面是此时此刻的学习心得~*/
/*没什么好说的 看看题目就明白递归是怎么回事了~*/
题目：求问题Z
思考：
（1）我们发现：要想解决问题Z，只需要解决稍简单点的问题Y，要想解决问题Y只需解决稍简单点的问题W，
要想解决问题W只需解决稍简单点的问题V，要想解决问题V只需解决稍简单点的问题U
…………要想解决问题B只需要解决稍微简单点的问题A。
（2）我们发现：从Z到Y再到W再到V…………再到A都遵循同样的规律。
（3）我们发现：问题A可以相当容易的得到结果。
因此只要告诉计算机（2）（3），计算机就一定会告诉我们答案。
今天首先了解了递归的概念，如上，概似高中数学学的数列的递推公式- -，还是很通俗易懂的。
但是无奈应了那句话----“看得明，写不出”。
因此想要真正灵活的掌握递归思想，一定是需要做题写程序来积累的。
（为服务于本文，下面的程序都用递归来写，虽然有的用递归是个很糟糕的选择= =#）
从题目中去感悟~~~
Q1：求n！
要想知道n！[因为n！=n*（n-1）！]所以就要先知道（n-1）！[因为（n-1）！=（n-1）*（n-2）！]]所以就要先知道（n-2）！…………最后只需知道1！即可。
符合本文开头所说的（2）（3），所以可以用递归来解决。
按照本文开头所说，只需告诉计算机（2）（3）即可。
1 （n=0时）
即 n！=
nx（n-1） （n=1，2，3…时）
转化成程序语言即：
1 #include<iostream.h> 2 int factorial(int n) 3 { 4 int y; 5 if(n==0) y=1; 6 else y=n*factorial(n-1); 7 return y; 8 } 9 void main() 10 { 11 int n; 12 cin>>n; 13 cout<<factorial(n)<<endl; 14 }
Q2：经典的汉诺塔：ABC三根柱子，将n个圆盘从A移动到B，可以借助C。（一次只能移动柱子最上端的一个圆盘；小圆盘上不能放大圆盘）
要想将n个盘子从A移动到B，可以a：将n-1个盘子从A移动到C。b：将最下面的即第n个盘子从A移动到B。c：将n-1个盘子从C移动到B。
（由此可见要想解决n个盘子的移动，只需要解决n-1个盘子的移动）
n-1个盘子的移动也可以照搬上面，只需要解决n-2个盘子的移动…………要想解决2个盘子的移动，只需要解决1个盘子的移动。
符合本文开头所说的（2）（3），所以可以用递归来解决。
按照本文开头所说，只需告诉计算机（2）（3）即可。
1 （n=1）
f（n）=
f（n-1）+1+f（n-1） （n=2，3，4…）
转化成程序语言即：
#include<iostream.h> void hanoi(int n,char a,char b,char c) { if(n==1)cout<<a<<"->"<<b<<‘ ‘; else { hanoi(n-1,a,c,b); //将n-1个从A移到C cout<<a<<"->"<<b<<‘ ‘; //将第n个从A移到B hanoi(n-1,c,b,a); //将n-1个从C移到B } } void main() { int n; cin>>n; hanoi(n,‘A‘,‘B‘,‘C‘); }
Q3：斐波那契数列。
鸡个数问题：一 小鸡出生第三天生下一只小鸡。假设第一天只有一只刚出生的小鸡，问第n天一共有多少只鸡。
要想递归，关键是找到每一层之间的结构规律！！！经分析得第n天鸡的个数等于第n-1天鸡的个数 加上 n-2天前存在的鸡在第n天生下的小鸡数
因此要想知道第n天鸡的个数只需要知道第n-1天和第n-2天…………以此类推，最终只需要知道第0天和第1天鸡的个数。
0（n=0）
f（n）= 1（n=1）
f（n-1）+f（n-2） （n=2，3，4，5…）
转化成程序语言即：
1 #include<iostream> 2 using namespace std; 3 int num(int day) 4 { 5 6 if(day==0)return 0; 7 if(day==1)return 1; 8 return num(day-1)+num(day-2); 9 10 } 11 void main() 12 { 13 int day; 14 cin>>day; 15 cout<<num(day)<<endl; 16 }
一次走1阶或者2阶，爬n层阶梯的方法
分析得，如果最后一步为1阶，只需要知道爬n-1层的方法；如果最后一步为2阶，只需要知道爬n步的方法。
因此f（n）=f（n-1）+f（n-2） 又是斐波那契数列~~！
音符问题：若将4分音符打n拍的时间，用4分音符和2分音符来填充，共有多少种节奏？（4分音符的时值是2分音符的1/2）
分析得，如果最后的是四分音符则只需要知道n-1拍共有多少种节奏；如果最后是二分音符，则只需要知道n-2拍共有多少种节奏。
因此f（n）=f（n-1）+f（n-2） 和爬楼梯毫无二致 斐波那契数列。
Q4：画树（共n层枝丫）：树的树干叉开长出两根树枝，每根树枝又叉开长出两根树枝，每根树枝又叉开长出两根树枝…………
发现递归结构：一个树枝分叉成两个树枝
再次强调：递归，把握结构是关键！！！！
分析：从树冠到树干依次是第1到n层。
f（画n层）=画第n层+f（画n-1层）
f（画n-1层）=画第n-1层+f（画n-2层）
……
最后推至
f（画1层）=画第1层+f（画0层）
f（画0层）=什么也不画
符合本文开头的（2）（3），每层存在一定的规律，可逐步简化，并且简化的最终问题可解。
代码如下：
1 void drawtree(int n) //画n层的树的枝丫 2 { 3 if(n==0); 4 else 5 { 6 left(); //左转 7 forward(n); //前进n步，画第n层的树枝 8 drawtree(n-1);//画n-1层的树的枝丫 9 back(n); //后退n步 10 right(); //右转 11 12 right(); //右转 13 forward(n); //前进n步，画第n层的树枝 14 drawtree(n-1);//画n-1层的树的枝丫 15 back(n); //后退n步 16 left(); //左转 17 18 19 } 20 }
Q5：把一个整数转换为字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，‘7’
递归在这里有改变字符输出顺序的作用~
1 #include<iostream> 2 using namespace std; 3 void f(int n) 4 { 5 char c=n%10+48; 6 if(n/10==0)cout<<c<<‘ ‘; 7 else 8 { 9 f(n/10); 10 cout<<c<<‘ ‘; 11 } 12 } 13 int main() 14 { 15 int num; 16 cin>>num; 17 f(num); 18 return 0; 19 }
Q6：判断奇数还是偶数（递归不仅包含自己调用自己，还有交互递归，见代码）
1 #include<iostream.h> 2 bool iseven (int); 3 bool isodd(int n) 4 { 5 return !iseven(n); 6 } 7 bool iseven(int n) 8 { 9 if(n==0)return true; 10 else return isodd(n-1); 11 } 12 void main() 13 { 14 int n; 15 cin>>n; 16 cout<<isodd(n); 17 }
Q7：二分查找（指数爆炸的威力大家都知道吧，二分法在大量数据中进行查找时会发挥巨大的威力！）
二分查找具体怎么回事，直接上例子就明了了，因为每一次查找都用一样的方式，所以其中一定要用到递归。
e.g.
/*在0~999中找500这个数*/ #include<iostream.h> int bin_search(int*p,int low,int high,int key); void main() { int a[1000]; for(int i=0;i<1000;i++)a[i]=i; cout<<bin_search(a,0,999,2000)<<endl; //2分法查找 } int bin_search(int*p,int low,int high,int key ) { int mid=(low + high) / 2; if(p[mid]==key)return 1; //要找的数正好是中值 if (low > high) return 0; if(key>p[mid])bin_search(p,mid+1,high,key);//要找到数大于中值 所以缩小查找范围 再进行二分查找 else bin_search(p,low,mid-1,key);//要找的数小于中值 所以缩小查找范围 再进行二分查找 }
Q8：判断回文数。
分析：
将要判断的数字放入数组中。
每次判断数组两端的元素是否相等，如果不相等则不是回文数，
如果相等则去掉两端的元素，再判断剩下的数组中两端的元素是否相等……
直到只剩下0个元素（偶数个元素的数组）或者1个元素（奇数个元素的数组），是回文数。
#include<iostream.h> #include<string.h> int f(int low,int high,char*p,int length); void main() { char c[]="apepa"; int length=strlen(c); cout<<f(0,length-1,c,length)<<endl; } int f(int low,int high,char*p,int length) { if (length == 0 || length == 1) return 1; if (p[low] != p[high]) return 0; return f(low+1, high-1, p, length-2); }
下面给出字符串反转的一个例子（与判断回文数的思路完全相同）（当然本文开头说过有些程序用递归不是一个好选择，举出这些列子只是为了加深理解递归）
#include <iostream> using namespace std; int str_turn(int low, int high, char *p, int length) { char temp; if (length == 1 || length == 0 ) { return 0; } p[low] = p[high]; p[high] = temp; return str_turn(low+1, high-1, p, length-2); } int main() { char str[]="test"; str_turn(0, strlen(str)-1, str, strlen(str)); cout << str; return 0; }
做了这些题之后，虽然都是一些很简单的小题目，但是也算从不知道什么是递归到与递归相识相知啦~_~，也领略了它的一些神奇的魅力~~~
所以贴出来，和大家一起分享~
因为是初学，所以本文只能在最简单的层面上来运用递归，但是自以为对初学来说是相当有益的~希望对大家的递归入门有所帮助啦~~~~
感谢http://blog.csdn.net/cbs612537/article/category/1287535 ~ 对我的入门帮助很大~