华师一附中OI组

标题: 递归大楼 [打印本页]
作者: admin    时间: 2020-2-6 13:58
标题: 递归大楼
函数自己调用自己叫做递归，递归是解决问题的通用方法之一。


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

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

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

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

  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    时间: 2020-2-6 13:58
再来看一个例子，

小孩子的加法：假设我们要计算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    时间: 2020-2-6 14:05
再来一个经典的例子，回文串的判断，所谓回文串，就是颠倒之后和原来是一样的字符串，我们以前的做法是用两个指针，分别从头和尾向中间移动来判断。但这次，我们用一个新的做法：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    时间: 2020-7-23 10:06
1、无聊的加法
2、n!的另外一种求法
3、GCD
4、十进制转十六进制
5、不用数组颠倒输入的数字
6、HANOI
7、10个数中的最大数
8、选择排序也可以递归
作者: admin    时间: 2020-7-23 15:18
再来看一个十进制转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    时间: 2020-7-23 15:32
递归是初学者很难理解的一个知识点，但是必须去认真掌握。因为递归会让很多的程序段变得简单和易读。
以下都是经典的递归的例子：
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    时间: 2023-1-4 17:37
再看一个有趣的例子，求一个正整数的位数：
一般的做法是把这个正整数除以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. }
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2