这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n -[(1-√5)/2]^n}（又叫“比内公式”，是用无理数表示有理数的一个范例。）（√5表示根号5）     有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。

    用数学公式表示出来就是：           F（1）=1，F（2）=1     (n=1,2)          F(n)=F(n-1)+F(n-2)     (n>2)

     有三种比较常用的求解第n项斐波那契数列的方法：递归法、迭代法、通项公式法。

1、递归法

概述　　递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰.。

　　程序调用自身的编程技巧称为递归（ recursion）。

　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

　　注意：

　　(1) 递归就是在过程或函数里调用自身;

　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　递归的另一种定义：

　　递归，就是用自己的简单情况，定义自己。

　　在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

　　例如，下列为某人祖先的递归定义：

　　某人的双亲是他的祖先（基本情况）。 某人祖先的双亲同样是某人的祖先（递归步骤）。斐波那契数列是典型的递归案例：

　　Fib(0) = 0 [基本情况] Fib(1) = 1 [基本情况] 对所有n >1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义]尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：

　　阶乘(1) = 1 [基本情况] 对所有n > 1的整数：阶乘(n) = (n *阶乘(n-1)) [递归定义]一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。

　　如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

递归应用　　递归算法一般用于解决三类问题：

　　(1)数据的定义是按递归定义的。(Fibonacci函数)

　　(2)问题解法按递归算法实现。(回溯)

　　(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)

　　递归的缺点：

　　递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 这种方法的优点是简洁和容易理解，缺点是时间复杂度太大，随着n的增大，运算时间将会急剧增加。因此在很多场合这种方法是不可取的。 使用这种方法的关键代码是： if(n == 1|| n== 2) {     return1; } else {     return fib(n- 1) + fib(n - 2); }

#include int main() {     longint  fib[41] = {0,1};     inti;

   for(i=2;i