递归的运用

发表于 | 分类于

一、递归的相关点

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

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

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

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

1.2递归是怎么实现的？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#二、练习

##1、进制转换

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

###1.1、递归算法

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

此处输入图片的描述

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

所以代码如下：

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

	transfrom(x/n,n);
	if (x%n<9)			//每次递归输后出余数
		cout<<x%n;
	else
		cout<<char(x%n+55);
		
}

main中测试:

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

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

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

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

1
2
3
4
5
6
7
8
cout<<"栈操作："<<endl;
cout<<endl;
transfrom_1(171,16);
cout<<endl;
transfrom_1(2147483647,8);
cout<<endl;
transfrom_1(2147483647,2);
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* int' Fibonacci(int n)
* 计算斐波那契数列的值
* 采用递归的方式
* @param[in]  n 项数
* @param[out]T x
*/
long Fibonacci(int n)
{
	if (n==0)
		return 0;
	else if (n==1)
		return 1;
	else
		return Fibonacci(n-1)+Fibonacci(n-2);
}

测试函数：

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

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

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

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

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

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

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

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

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

###3.1、递归算法
看得出，除了两边的数，其余的都是上边两数字的和，所以：

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

所以代码设计十分之简单

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

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

主函数测试打印：

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

测试结果：

此处输入图片的描述

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

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

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

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

##4、全排列
定义相信都很熟悉，不再阐述。

###4.1、问题分析
全排序1~4，就是4个首位交替，并且降低规模，重新交替，再降低规模

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

###4.2、递归算法
所以代码如下：

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

测试函数：

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

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

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

main中测试:

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

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

##6、格雷码（GRAY）

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

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

###6.2、递归算法
所以，代码如下：

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

测试函数：

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

	TraGray(N);

	for (int i=0;i<M;i++)
	{
		for (int j=N-1;j>=0;j--)
			cout<<result[i][j];
		cout<<endl;
	}
	return 0;
}

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