递归就是根据任务的相似性,将一个大任务,划分成多个相似的小任务,然后一一进行操作。
主要分为两步: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; }