递归法

藏宝库编辑 · 2024-9-2 10:06:34

什么是递归算法？
若一个算法直接的或间接的调用本身本身，则称这个算法是递归算法。递归本质上也是一种循环的算法结构，它把较复杂的盘算逐次归结为较简朴的情况的盘算，直到归结到最简朴情况的盘算，并终极得到盘算效果为止。
递归算法的特性
比方，我们现在要求n!那么这个标题就可以转化成求n(n-1),而我们要求(n-1)!又可以转化成求(n-1)(n-2)，有规律的递减，直到1！然后竣事。递归算法的实行过程分别为递推和回归两个阶段。在递推阶段，把规模为n的标题的求解推到比原标题的规模较小的标题求解，且必须要有停止递归的条件。在回归阶段，当得到最简朴环境的解后，逐级返回，依次得到规模较大标题的解。

（1）求解规模为n的标题可以转化为一个或多个结构雷同、规模较小的标题，然后从这些小标题的解能方便地构造出大标题的解。
（2）递归调用的次数必须是有限的。
（3）必须有竣事递归的条件（边界条件）来停止递归。
斐波那契数列标题
1.标题形貌
著名的数列—斐波那契数列（Fibonacci），可以界说为：
当n = 0时；F(n) = 0。（从实际意义出发，不考虑n<0的环境）
当n = 1时；F(n) = 1。
当n > 1时；F(n) = F(n-1)+F(n-2)。

哀求出第n项斐波那契数，以及前n项斐波那契数列的和（在没有兔子殒命的抱负环境下）。
2.分析
从上面的规律我们可以得到一个无穷数列（1，1，2，3，5，8，13，21，34，55……），求解第n个斐波那契数，必须先盘算F(n-1)和F(n-2)，而盘算F(n-1)和F(n-2)又必须先盘算F(n-3)和F(n-4)，以此类推，直至F(1)和F(2)，而F(1)和F(2)是可以立刻求得，因此该标题可以利用递归方法求解。
3.步伐运行
#include<iostream>using namespace std;int fib(int n){ int f=0; if(n==1||n==2) return 1; //第一个月兔子没有成熟，不出生新兔子，第二个月成熟了，只有一对成熟兔子, //我们也可以这么写：if（n<=1）return n; f=fib(n-1)+fib(n-2); //n>=3时，当月兔子数便是前一个月兔子数目加上上月兔子数 return f;}int main(){ int n,i,m=0; cin>>n; m=fib(n); cout<<"第"<<n<<"项是"<<m<<endl; m=0; for(i=1;i<=n;i++) m=fib(i)+m; cout<<"前"<<n<<"项和是"<<m<<endl; return 0;}至此我们已经能求出第n项斐波那契数，以及前n项斐波那契数列的和了。

递归法

所属分类: 问答交流

新帖推荐: 30日

推荐作品