裴波那契数列 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程序测试如下：
$origin = 6;
$result = sum($origin);
echo $result;
function sum($n)
{
if($n < 3)
{
return 1;
}
else
{
$base1 = 1;
$base2 = 1;
$temp;
for($i=3; $i <= $n; $i++)
{
$temp = $base2;
$base2 += $base1;
$base1 = $temp;
}
return $base2;
}
}
?>