用递归来替代循环

递归就是根据任务的相似性,将一个大任务,划分成多个相似的小任务,然后一一进行操作。

主要分为两步:1.找到任务的相似性,进行划分 2.设置出口,制定一个循环终止点

例子一:

#include<iostream>
using namespace std;
int main()
{
	for(int i=0;i<10;i++)
	{
		cout<<i<<endl;
	}
	return 0;
}

该任务是输出0~9,这是一个大任务;

1.找到任务的相似性

该任务可以划分成先输出0,然后输出1~9;然后输出1~9又可以划分成输出1,然后输出2~9;然后输出2~9又可以划分成输出2,输出3~9……

2.找到出口

递归没有的出口的话,就成了死循环,没有任何意义。

阶段1找到了任务的相似性,即每个任务都由输出一个数a和输出a+1~n(a+1<n)两部分组成,出口就是递归到不满足相似性条件的地方,即当a+1 >= n的时候,到达出口。

等价的递归程序:

#include<iostream>
using namespace std;
void fun(int begin,int end)
{
	if(begin >= end)return;
	cout<<begin<<endl;
	fun(begin+1,end);
}
int main()
{
	fun(0,10);
	return 0;
}

例子二:

#include<iostream>
using namespace std;
int main()
{
	string str;
	char temp;
	int len;
	cin>>str;
	len = str.length();
	for(int i=0;i<len/2;i++)
	{
		temp = str[i];
		str[i] = str[len-1-i];
		str[len-1-i] =temp;
	}
	cout<<str<<endl;
	return 0;
}

输入:abc

输出:cba

这个大任务是进行len/2次字符交换操作;

1.找到任务的相似性

将0~len之间的字符交换可分为:先将第0个和第len-1个字符交换,然后将1~len-2之间的字符交换;将1~len-2之间的字符交换可分为将1和len-2的字符交换,然后将2~len-3之间的字符交换……

2.找到出口

由阶段一发现,每个任务都是由交换第i和len-1-i个字符,以及交换i+1和len-1-i-1之间的字符,两部分组成,但是i+1要小于len-1-i-1,才有之间的字符,所以这就是出口。

等价的递归程序:

#include<iostream>
using namespace std;
void fun(char *begin,char *end)
{
	if(begin>=end)return;
	char  temp;
	temp = *begin;
	*begin = *end;
	*end = temp;
	fun(begin+1,end-1);
}
int main()
{
	string str;
	char temp;
	int len;
	cin>>str;
	len = str.length();
	fun(&str[0],&str[len-1]);
	cout<<str<<endl;
	return 0;
}


用递归来替代循环

上一篇:LeetCode | Largest Rectangle in Histogram


下一篇:UI控件的位置操作