递归大楼

admin

函数自己调用自己叫做递归，递归是解决问题的通用方法之一。


生活里面也有很多的递归的例子，比如说要求10个数字里面的最大数，我们可以先求出前九个数的最大数，然后把它和第10个数进行比较判断谁更大。而求前面9个数的最大数又可以先求出前面8个数的最大数，然后和第9个进行比较，***，求前两个数的最大数就是前1个数的最大数和第2个数进行比较，最后(!)求前一个数的最大数，那就是自己。这样一个思维就是递归的思维。

与之对应的是递推的思维：第一个数假设就是最大的，然后它和第二个数进行比较，留下一个最大的，然后它又和第3个数进行比较，留下最大的，***，直到第10个数比较完成。

看得到：相同的的方式他们都有一个终点，但递归的终点是n=1，递推的终点是n=10。
最明显的区别是 递归是由大到小处理问题，递推是由小到大。

看看两个程序的写法，对比感觉下它们的异同。

1. 
   
2. int a[]= {0,1,3,7,4,8,9,0,5,6,2}; ///第一个0不用
   
3. int getmax1(int n) ///求前n个数的最大数递归做法
   
4. {
   
5.         if(n==1) return a[1]; ///一个数的最大数当然是自己
   
6.         else
   
7.                 {
   
8.                         int t=getmax1(n-1); ///求出前面n-1个的最大
   
9.                         if (a[n]>t) t=a[n]; /// 和这个数比较再求最大
   
10.                         return t;
    
11.                 }
    
12. }
    
13. int getmax2(int n) ///求前n个数的最大数递推做法
    
14. {
    
15.         int t=a[1];
    
16.         for (int i=2; i<=n; i++)
    
17.                 if (a[i]>t)  t=a[i];
    
18.         return t;
    
19. }
    

复制代码

在代码上看得到，递归做法n值是由大到小，没有使用循环，而是自己调用自己。递推做法i值由小到大，用的是for循环。

admin

再来看一个例子，

小孩子的加法：假设我们要计算4+3的值，小孩子有种做法是在桌面上先摆两堆石头，分别是4个（左边）和3个（右边），然后开始计算：
1、右边有3个，还没有合成为一堆，拿一个过来，左边5个，右边2个
2、右边有2个，还没有合成为一堆，拿一个过来，左边6个，右边1个
3、右边有1个，还没有合成为一堆，拿一个过来，左边7个，右边0个
4、右边有0个，已经合成为一堆，答案是7
这个做法虽然有人觉得很无聊，但是思路是值得学习的，也是一种由大到小的递归思维和计算过程。写成程序：

1. int add(int x,int y)
   
2. {
   
3.         if (y==0) return x;
   
4.         else return add(x+1,y-1);
   
5. }

复制代码

2的幂分解
国王的魔镜
外星密码

admin

再来一个经典的例子，回文串的判断，所谓回文串，就是颠倒之后和原来是一样的字符串，我们以前的做法是用两个指针，分别从头和尾向中间移动来判断。但这次，我们用一个新的做法：1、长度为0或者1的字符串肯定是回文的
2、若第一位和最后一位不相等，则一定不是回文
3、若第一位和最后一位相等，则看去掉第一位和最后一位剩下的那个串是不是回文。

翻译成代码就是：

1. bool isr(string s)
   
2. {
   
3.         int l=s.size();
   
4.         if (l<=1) return 1; //长度为0或者1的肯定是
   
5.         if (s[0]!=s[l-1]) return 0;//首尾不等肯定不是
   
6.         t=s.substr(1,l-2); ///去掉首尾得到t
   
7.         return isr(t);///判断t
   
8. }

复制代码

admin

1、无聊的加法
2、n!的另外一种求法
3、GCD
4、十进制转十六进制
5、不用数组颠倒输入的数字
6、HANOI
7、10个数中的最大数
8、选择排序也可以递归

admin

再来看一个十进制转2进制的精妙算法：把十进制数X转换成二进制可以用短除法：
若x==0，则转换结束，否则把x除以2，得到的余数是二进制的最低位，剩下的数作为新的x继续去做
写成代码段：

1. void zh(int  x)
   
2. {
   
3.         if (x>0)
   
4.         {
   
5.                 zh(x/2);
   
6.                 cout<<x%2;
   
7.         }
   
8. }

复制代码

这样写也不错，将x转成s

1. string zh(int x)
   
2. {
   
3.         if (x==0) return "0";
   
4.         else if (x==1) return "1";
   
5.         else
   
6.         {
   
7.                 char ch=x%2+'0';///最末尾那位
   
8.                 return (zh(x/2)+ch);
   
9.         }
   
10. }

复制代码

两种写法思想是一样的，表现形式有些不同，大家好好体会下。

admin

递归是初学者很难理解的一个知识点，但是必须去认真掌握。因为递归会让很多的程序段变得简单和易读。
以下都是经典的递归的例子：
1、快速幂  http://hsyit.cn/forum.php?mod=viewthread&tid=40
2、最大公约数GCD [url=http://hsyit.cn/forum.php?mod=viewthread&tid=15[/url]
3、二分查找
4、HANOI汉诺塔问题
5、输入一个字串颠倒输出  http://hsyit.cn/forum.php?mod=viewthread&tid=69257

admin

再看一个有趣的例子，求一个正整数的位数：
一般的做法是把这个正整数除以10，若商不为0的话就位数+1，直到商为0，可以通俗的理解为，每次砍掉最后一位，直到没有，砍了多少次，就是几位数，很好理解。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         int x;
   
6.         cin>>x;
   
7.         int k=0;
   
8.         while (x>0)
   
9.                 {
   
10.                         x=x/10; //砍掉最后一位
    
11.                         k++;//位数+1
    
12.                 }
    
13.         cout<<k;
    
14.         return 0;
    
15. }

复制代码

但是我们另外，想一想，可不可以这样做呢：如果x<10就是一位数，>10的话就除以10，位数就等于商的位数+1

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int W(int x)
   
4. {
   
5.         if (x<10) return 1;//<10就是一位数
   
6.         else return W(x/10)+1; //除以10的商的位数+1
   
7. }
   
8. int main()
   
9. {
   
10.         int x;
    
11.         cin>>x;
    
12.         cout<<W(x);
    
13.         return 0;
    
14. }

复制代码