斐波那契数列的递推公式是怎样的？

本文共计871个文字，预计阅读时间需要4分钟。

我们已知斐波那契数列（又称兔子数）是一组有趣的数字，首项为1，第二项也为1，之后每一项都是前两项之和。那么，如何实现输入第n项就打印出其对应的斐波那契数呢？下面是一个递归实现的简单示例：

我们都知道斐波那契数（也叫兔子数）是一组十分有趣的数字，首相为1，第二项也是1，之后的每一项就是前两项之和，那么该如何实现输入第n项就打印其对应的斐波那契数字呢？

递归实现

事实上，要实现斐波那契数的打印并不困难，最简单的思路就是递归。

递归就是将斐波那契数计算过程进行提炼，进而得出一段递归。

代码如下：

#include<stdio.h>int fabonacci(int n){ if (n == 1 || n == 2) return 1;//第一项和第二项直接返回1 else return fabonacci(n - 1) + fabonacci(n - 2);}int main(){ int n = 0; while (~scanf("%d",&n)) { printf("%d\n", fabonacci(n)); } return 0;复制代码

要想得出递归的思路最重要的就是掌握递归的核心：大事化小！

可是,递归就可以完全解决斐波那契数吗？

事实上，当我们输入50，既要打印第50项的数字时，递归的代码就会要运算很长的时间，这是因为递归不会记住之前的项的结果，所以求的项数越大，就会进行越多的重复计算，就会严重拖慢结果的打印时间。