不使用递归如何求裴波那契数列

裴波那契数列 1，1，2，3，5，8，13，21…………，一般来说使用递归会使问题简单很多。但是有些时候会要求我们不用递归解决这类问题，比如Lisp这种不支持递归的语言，或者对程序的执行效率要求很高，或者面试等等场合。本文给出一种不使用递归求解裴波那契数列的方案。

下面是递归的解法：

public int sum(int n)
{
　　if(n<3)
　　　　return 1;
　　else
　　　　return sum(n-1) + sum(n-2);
}

不使用递归的话可以用下面的函数实现：

public int sum(int n)
{
　　if(n<3)
　　　　return 1;
　　else
　　{
　　　　int base1 = 1;
　　　　int base2 = 1; int temp;
　　　　for(int i=3; i<=n; i++)
　　　　{
　　　　　　temp = base2;
　　　　　　base2 += base1;
　　　　　　base1 = temp;
　　　　}
　　　　return base2;
　　}
}

PHP程序测试如下：

本文地址：http://www.nowamagic.net/librarys/veda/detail/364，欢迎访问原出处。