文档介绍：递归算法
递归的概念
先看大家都熟悉的一个民间故事:从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说,从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说……。象这样,一个对象部分地由它自己组成,或者是按它自己定义,我们称之为递归。
一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的。在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。
递归的特点与应用场合
用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。
递归的实现方法
递归是借助于一个递归工作栈来实现.
: 问题向一极推进,这一过程叫做递推;这一过程相当于压栈.
: 问题逐一解决,最后回到原问题,这一过程叫做回归。这一过程相当于弹栈.
void rever()
{ char c;
cin>>c;
if(c!='!')
{void rever()
{ char c;
cin>>c;
if(c!='!')
{void rever()
{ char c;
cin>>c;
if(c!='!')rever();
cout<<c;
}
}
cout<<c;
}
}
cout<<c;
}
int main()
{rever();}
输入:gn!
输出:_!ng___
#include <iostream>
using namespace std;
int fac(int a)
{
if(a==0)return 1;//初始条件
return a*fac(a-1);//递归公式
}
int main()
{ int n;
cin>>n;
cout<<fac(n);
return 0;
}
输入:5 输出:____
N=3时的递归过程
应用举例3—斐波那契数列
问题描述:有一对兔子,出生后一个月就可以长大,然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一对。 现在,我们有一对刚出生的这种兔子,那么,n个月过后,我们会有多少对兔子呢?假设所有的兔子都不会死亡。
输入:5
输出:5
:n=1或n=2时,F(n)=1
: F(n)=F(n-1)+F(n-2)
从上面的分析可以看到,第n个月后兔子的数目有两部分构成:
1、上月的所有兔子;
2、上月的所有老兔子所生的小兔子。
#include <iostream>
using namespace std;
int f(int k)
{
if(k==1)return 1;
if(k==2)return 1;
return f(k-1)+f(k-2);
}
int main()
{ int n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}
应用举例3—斐波那契数列
应用举例4—楼梯问题
例题:楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算上n阶台阶共有多少种不同的走法?
设n阶台阶的走法数为f(n)
:n=1 f(1)=1;n=2 f(2)=2
:f(n)= f(n-1) + f(n-2))