[关闭]
@rg070836rg 2018-07-06T14:36:45.000000Z 字数 5352 阅读 2343

递归的运用

data_structure

一、递归的相关点

1.1怎么去写一个递归函数?

我认为写一个递归函数，主要就是两点：

  • 什么时候出递归
  • 每一次递归前/后还要做哪些事情

下面的题目，尽量依靠这两点来分析。

1.2递归是怎么实现的？

在递归调用情况下，被调函数的局部变量采用动态分配存储区（每调用一次就分配一份，以存放当前使用的数据，当返回时随即释放）。我们把这个动态区称为运行栈。每次调用函数执行入栈操作，每次从函数返回时，执行出栈操作。

概括来讲，函数的调用可分为三个步骤：

  • 调用函数发送调用信息，包括调用方要传给被调方的信息，如传给形参的实参值，函数返回地址；
  • 分配被调方需要的局部数据区，用来存放被调方定义的局部变量，形参变量，返回地址等，并接收调用方传来的调用信息；
  • 调用方暂停，把计算控制力转移到被调方。

当被调方结束运行，返回调用方时，返回处理分为三个步骤：

  • 传送返回信息，包括被调方要传回给调用方的信息，如计算结果等；
  • 释放分配给被调方的数据区；
  • 按返回地址把控制转回给调用方；

1.3如何计算时间复杂度和空间复杂度？

一般的题目复杂度可以大致看看就能算出来，但是一旦比较难，就不能直接的看出来，下面链接是网上总结比较好的一篇博文，放在此留作参考。

递归算法的时间复杂度终篇

1.4关于递归与非递归的转化

递归实际上是非常非常的消耗空间的，每次递归就会开辟一个递归运行栈，很可能就会由于递归的次数太多初始默认的栈空间被耗尽。同时，也不会去建议为了递归而调高空间。

首先，我们需要先了解下，递归是如何调用的
递归调用的详细过程

那么对于一个问题，要怎么去把递归换成非递归？

  • 可以取一个特例
  • 分析哪些元素需要放在栈中
  • 分析栈的变化
  • 转化到普遍，编写算法

其实最重要的就是最后一部，如何把特例转化为普遍规律，这步是很难的，理论上，所有的递归都能用栈来解决，搞清楚递归调用树，分析每步的操作。

下面，链接一篇文章，详细的讲了该问题：算法设计中的递归与非递归转换

二、练习

1、进制转换

编写把十进制正整数转换为S进制(S=2，8，16)数输出的递归算法。
十进制转换为S进制的基本方法是“除基取余，上右下左”。

1.1、递归算法

  • 什么时候出递归
  • 每一次递归前/后还要做哪些事情

此处输入图片的描述

1、当新的被除数为0的时候，出递归；
2、每次递归输后出余数

所以代码如下：

  1. /**
  2. * void transfrom(int x,int n)
  3. }
  4. * 用于进制的转换
  5. * 采用递归的方式
  6. * @param[in]   x十进制数  n转的进制数
  7. * @param[out]T x
  8. */
  9. void transfrom(int x,int n)
  10. {
  11.     if(x==0) return ;//当新的被除数为0的时候，出递归；
  13.     transfrom(x/n,n);
  14.     if (x%n<9)          //每次递归输后出余数
  15.         cout<<x%n;
  16.     else
  17.         cout<<char(x%n+55);
  19. }

main中测试:

  1.     cout<<"递归操作："<<endl;
  2.     transfrom(171,16);
  3.     cout<<endl; 
  4.     transfrom(2147483647,8);
  5.     cout<<endl;
  6.     transfrom(2147483647,2);

测试截图：
此处输入图片的描述
复杂度很好分析，每次递归做的事情级别为O(1),一共递归了n次，所以是O(n).

1.2、非递归算法

下面提供一种非递归的方法，原来的递归是把数字反序输出，所以用栈，可以达到这个目的。

  1. /**
  2. * void transfrom_1(int x,int n)
  3. * 用于进制的转换
  4. * 采用栈的方式
  5. * @param[in]   x十进制数  n转的进制数
  6. * @param[out]T x
  7. */
  8. void transfrom_1(int x,int n)
  9. {
  10.     stack<int> tmp;
  11.     while(x!=0)
  12.     {
  13.         tmp.push(x%n);
  14.         x=x/n;
  15.     }
  16.     while (!tmp.empty())
  17.     {
  18.         if (tmp.top()>9)
  19.             cout<<char(55+tmp.top());
  20.         else
  21.             cout<<tmp.top();
  22.         tmp.pop();
  23.     }
  24. }
  1.     cout<<"栈操作："<<endl;
  2.     cout<<endl;
  3.     transfrom_1(171,16);
  4.     cout<<endl;
  5.     transfrom_1(2147483647,8);
  6.     cout<<endl;
  7.     transfrom_1(2147483647,2);
  8.     cout<<endl;

测试截图：
此处输入图片的描述

2、Fibonacci数列

2.1、数学定义：

斐波那契数列
F（0）=0，
F（1）=1，
F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）

2.2、递归分析

1、当新的数为1的时候，出递归；
2、每次返回结果

所以代码如下：

  1. /**
  2. * int' Fibonacci(int n)
  3. * 计算斐波那契数列的值
  4. * 采用递归的方式
  5. * @param[in]  n 项数
  6. * @param[out]T x
  7. */
  8. long Fibonacci(int n)
  9. {
  10.     if (n==0)
  11.         return 0;
  12.     else if (n==1)
  13.         return 1;
  14.     else
  15.         return Fibonacci(n-1)+Fibonacci(n-2);
  16. }

测试函数：

  1.     for (int i=0;i<30;i++)
  2.     {
  3.         cout<<Fibonacci(i)<<endl;
  4.     }

测试截图：
此处输入图片的描述
关于复杂度：
我们取F(n)看，发现能展开n-1层，每层又需要计算很多重复的东西，比如算f(100)需要重新算f(99)与f(98)，所以时间复杂度应该近似会为O(),空间复杂度，到后期，每增加一个维度，都会把前面的重新再算一遍，所以空间复杂度额也近似为O()

2.3、非递归算法

同样，这个也提供一种复杂度较低的非递归算法：

  1. long Fibonacci_2(int n)
  2. {
  3.     int a,b,c;      
  4.     a=1;b=1;
  5.     if (n==0)
  6.         return 0;
  7.     else if (n==1)
  8.         return 1;
  9.     for(int i=2; i<=n; i++)
  10.     {
  11.         c=a+b;
  12.         a=b;
  13.         b=c;
  14.     }
  15.     return c;
  16. }

很明显这个复杂度就降到了O(n)级别了，空间没有额外开辟为O(1);
分析下这个算法，这个方法每次只保存当前计算值的前两个数，不必像递归那般重复计算已经算过的值多次。那么，同样，可以用这种思路去优化递归算法。

2.4、递归算法的改进

并没有必要重复计算那么多次， 每个值只要计算一次即可，计算完存到一个数组里面，用的时候直接调。代码实现如下：

  1. /**
  2. * int' Fibonacci_1(int n)
  3. * 计算斐波那契数列的值
  4. * 采用数组记忆法，减少了重复计算的步骤，大大降低了时间复杂度
  5. * @param[in]  n 项数
  6. * @param[out]T x
  7. */
  8. long memory[100];
  9. long Fibonacci_1(int n)
  10. {
  11.     if (n==0)
  12.         return 0;
  13.     else if (n==1)
  14.         return 1;
  15.     if (memory[n]!=0) 
  16.         return memory[n];
  17.     return memory[n]=Fibonacci_1(n-1)+Fibonacci_1(n-2);
  18. }

这段代码，大大降低了原来递归的复杂度，和非递归相比，在计算多个值上比较有效率，而非递归的那种方法，只是在计算每个值时，效率比这段代码高。

3、杨辉三角

杨辉三角数为：
此处输入图片的描述

3.1、递归算法

看得出，除了两边的数，其余的都是上边两数字的和，所以：

  • 当每排第一个或者每排最后一个时，返回1出递归
  • 否则返回两递归之和

所以代码设计十分之简单

  1. int Triangle(int x,int y)
  2. {
  3.     if(y==1||y==x)
  4.         return 1;
  5.     else 
  6.         return Triangle(x-1,y-1)+Triangle(x-1,y);
  7. }
  8. /**

通过打印Triangle(i,j)就能得到第i行第j个数字。

主函数测试打印：

  1.     int RowCount,i,j,k;
  2.     cout << "请输入杨辉三角的行数:";
  3.     cin >> RowCount;
  4.     for(i = 1 ;i <=RowCount;i++)//从第0行开始
  5.     {   //打印第i行第一个元素前面的空格
  6.         for(k = 0;k < RowCount - i;k++)
  7.         {
  8.             cout << "    ";
  9.         }
  10.         for(j = 1;j <= i ;j++)//打印第i行的所有元素
  11.         {
  12.             cout << Triangle(i,j) << "       ";
  13.         }
  14.         cout << endl;
  15.     }

测试结果：

此处输入图片的描述

3.2、改进

当然，这样的复杂度也很高，每次都是把前面的工作全部重做，近似指数级指数。

同样，类似于Fibonacci数列，可以用记忆数组，把算过的全部存储起来。

  1. /**
  2. * int Triangle_1(int x,int y)
  3. * 用于求第x行第y个元素的值
  4. * 采用递归的方式，记忆数组辅助
  5. * @param[in]   x行  y列
  6. * @param[out]
  7. */
  8. int memory[100][100];
  9. int Triangle_1(int x,int y)
  10. {
  11.     if (memory[x][y]!=0)
  12.     {
  13.         return memory[x][y];
  14.     }
  15.     if(y==1||y==x)
  16.         return 1;
  17.     else 
  18.     {
  19.         memory[x][y]=Triangle(x-1,y-1)+Triangle(x-1,y);
  20.         return memory[x][y];
  21.     }
  22. }

这样，复杂度一下就降低到了O(n)级别了，效率已经算是很高了

4、全排列

定义相信都很熟悉，不再阐述。

4.1、问题分析

全排序1~4，就是4个首位交替，并且降低规模，重新交替，再降低规模

  • 只剩一位数，开始打印，退出递归
  • 递归前交换首位与后面的位置，递归后再交换回来

4.2、递归算法

所以代码如下：

  1. void FullArray(int k,int m)
  2. {
  3.     int i=0;
  4.     if(k==m)
  5.     {
  6.         for(i=0; i<=m; i++)
  7.             cout<<a[i];
  8.         cout<<"\t";
  9.         count++;
  10.         if(count % 5==0) 
  11.             cout<<endl;
  12.     }
  13.     else
  14.     {
  15.         for(i=k; i<=m; i++)
  16.         {
  17.             Swap(&a[k],&a[i]);
  18.             FullArray(k+1,m);
  19.             Swap(&a[i],&a[k]);
  20.         }
  21.     }
  22. }

测试函数：

  1. int main()
  2. {   
  3.     count=0;
  4.     for(int i=0; i<MaxNum; i++)
  5.         a[i]=i+1;
  6.     FullArray(0,3);
  7.     cout<<endl;
  8.     cout<<"1~"<<4<<"全排列总数为："<<count<<endl;
  9.     return 0;
  10. }

运行截图：
此处输入图片的描述
复杂度也是规模越大，前面做的活就越多，近似指数级了吧。

5、打靶问题

5.1、问题描述

一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？试用递归算法实现。

5.2、分析

其实这个问题是很好分析的，我要前n枪共打m环，那如果我最后一枪大了i环，就需要前n-1枪打了m-i环，所以问题化简就有了。

  • 当最后一枪需要打比10还要大，无解，返回0
  • 当最后一枪需要小于等于10，唯一解，返回1
  • 当总环数比枪数的10倍还要大，无解，返回0
  • 当总环数刚好等于10倍枪数，唯一解，返回1
  • 然后考虑当前枪会达到i环，递归到下一个子问题，中间用计数器记上总数

具体实现：

  1. /**
  2. * int GetN(int Sum, int n)
  3. * 获得可能的方法述
  4. * 采用递归的方式
  5. * @param[in]  所给总分Sum 所给次数n
  6. * @param[out]T x
  7. */
  8. int GetN(int Sum, int n)
  9. { 
  10.     int k=0;
  11.     if  (Sum>n*10) return 0;
  12.     if  (Sum==n*10)return 1;
  13.     if  (n == 1 &&  Sum >= 0 && Sum <= 10)  //若只打一枪，并且环数在0-10之间，只有一种可能性，返回1
  14.         return 1;
  15.     if (n==1 &&  Sum > 10 )
  16.         return 0;
  17.     else            
  18.     {
  19.         for(int i = 0; i <= 10; i++)        
  20.         {
  21.             k += GetN(Sum-i, n - 1);
  22.         }
  23.         return k;
  24.     }
  25. }

main中测试:

  1. int main()
  2. {
  3.     cout<<GetN(90,10)<<endl;
  4.     return 0;
  5. }

测试结果如图：
此处输入图片的描述

6、格雷码（GRAY）

6.1、问题分析

格雷码是在数电中第一次接触到的，当时还为怎么记所困扰，现在看来，很简单。
格雷码的定义是，每次变化只翻转一位。
通过观察，会发现：
此处输入图片的描述

  • 当只有一位时，输出0,1
  • 递归后，把当前列前一半填0，当前列后一半填1，前几列逆序

6.2、递归算法

所以，代码如下：

  1. void TraGray(int n)
  2. {
  3.     int m=pow(2,n);
  4.     //退出条件
  5.     if (n==1)
  6.     {
  7.         result[0][0]=0;
  8.         result[1][0]=1;
  9.     }
  10.     else
  11.     {
  12.         //缩小问题规模
  13.         TraGray(n-1);
  14.         //当前列前一半填0
  15.         for (int i=0;i<m/2;i++)
  16.             result[i][n-1]=0;
  17.         //当前列后一半填1
  18.         for (i=m/2;i<m;i++)
  19.             result[i][n-1]=1;
  20.         //前几列逆序
  21.         for (i=m/2;i<m;i++)
  22.             for (int j=0;j< n-1;j++)
  23.                 result[i][j]=result[m-1-i][j];
  24.     }
  25. }

测试函数：

  1. int main()
  2. {
  3.     int N,M;
  4.     cout<<"请输入格雷码位数"<<endl;
  5.     cin>>N;
  6.     if (!(N>0&&N<=6))
  7.     {
  8.         cout<<"只支持6位"<<endl;
  9.         N=6;
  10.     }
  11.     M=pow(2,N);
  13.     TraGray(N);
  15.     for (int i=0;i<M;i++)
  16.     {
  17.         for (int j=N-1;j>=0;j--)
  18.             cout<<result[i][j];
  19.         cout<<endl;
  20.     }
  21.     return 0;
  22. }

测试结果：
此处输入图片的描述

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注