- 递归函数是将规模较大的问题化为多个规模较小的同类问题。
- 递归函数的特征是定义中包含函数本身和必须有终止条件。
- 递归调用分为两个阶段,递推和回归。
【递推:将大问题转化为多个小问题,将问题逐步由未知化为已知。
回归:从已知出发,是递推的逆过程,逐个求值,到达递推的开头,解决问题。】
题目1:计算一个非负数n!
分析:要计算n!,只需要计算(n-1)!,n!=n*(n-1)!
计算(n-1)!,只需要计算(n-2)!,(n-1)!=(n-1)*(n-2)!
~and so on~
计算2!,只需要计算1!,2!=2
这就是递推!倒回去回归就能解决问题~
代码如下:
#include<iostream>
using namespace std;
int f(int n)//调用函数的一般形式,f表示被调函数名,括号内的int x是实参,返回值为int型。
{
int sum=1;
if(n==1)//终止条件。
{
return 1;
}
sum=n*f(n-1);
return sum;
}
int main()
{
int n;
cin>>n;
cout<<f(n);
return 0;
}
题目2:Hanoi塔问题
题目描述:有ABC三根柱子,A有n个大小不一样的盘子,大盘在下小盘在上,现要将A上的盘子移到C上,每次只能移动一个盘子,任何一个柱子都能放盘子必须满足大盘在下小盘在上的原则。
利用编程实现盘子的移动过程,n由用户输入。
分析:如果A柱只有两个盘子,那么A柱最上的一个盘子移到B上,另一个移到C上,再把B上的移到C上,
如果A上有三个盘子,那么需要将A柱最上面的盘子放在C柱上,将A柱中间的盘子放在B柱上,再将C柱上的盘子放在B柱上,将A柱最大的盘子放在C柱上。此时的B柱有两个盘子,重复类似A柱有两个盘子的操作即可,
最后可以发现:
- 将A柱上(n-1)个盘子移到B柱
- 将A柱最大一个盘子移到到C柱
- 将B柱上(n-1)个盘子移到C柱
- 其中第1步的移动(n-1)个盘子同样可以分为以上三步重复
【将问题逐步化为递归过程】
#include<iostream>
using namespace std;
int step=1;//计算step的总数需要定义全局变量,在move的前面
void move(char x,char y)
{
cout<<step<<x<<"-->"<<y<<endl;
step++;
}
void hanoi(int n,char a,char b,char c)
{
if(n==1)
{
move(a,c);//调用move函数,将a上唯一盘子移到c
}
else
{
hanoi(n-1,a,c,b);//将n-1个盘子从a移动到b
move(a,c);//调用move函数,将a中剩余盘子移动到c
hanoi(n-1,b,a,c);//将b中n-1个盘子移动到c
}
}
int main()
{
int n;
cout<<"请输入盘子的个数:";
cin>>n;
hanoi(n,'a','b','c');
return 0;
}
一点理解:
hanoi的意义就是hanoi(n,a,b,c)将n个盘子从a移动到c上,如果变成hanoi(n,a,c,b)就是将n个盘子从a移到b上,这是hanoi函数固定的意义。
先运行main函数,在main函数中需要调用hanoi函数,运行hanoi函数又需要调用move函数,整个代码是由下往上运行的。
题目3:Fibonacci问题
问题描述:
数列:1 1 2 3 5 8…
前两项为1 1,之后每一项都是前两项之和
用编程实现前n个fibonacci数,n由用户输入。
分析:
要求f(n),先求f(n-1)和f(n-2)
逐步往前推,推到f(1)和f(2)等于已知的1
#include<iostream>
using namespace std;
long recursion(int n)
{
if(n==1||n==2)
{
return 1;
}
else
{
return recursion(n-1)+recursion(n-2);
}
}
int main()
{
int n,i;
cout<<"求fibonacci前多少项"<<endl;
cin>>n;
for(i=1;i<=n;i++)
cout<<recursion(i)<<'\t';//'\t'是水平制表符
return 0;
}
一点理解:
还是从main函数开始理解函数,main函数中涉及到recursion函数便开始调用recursion函数,调用recursion函数时,重点在于else部分,由于else中得到recursion(n-1)这种带n的无意义数,于是继续调用自身函数,循环下去,直到得到recursion(1)和recursion(2),这两个都是已知为1的,到这里计算机内部运行就再倒推就好了。【递推和回归,这就是调用,递归都是这么个理~】