PHP学习 -- 两种方法实现斐波那契数列

什么是斐波那契数列

斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。

斐波那契数列指的是这样一个数列
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…… 这个数列从第3项开始，每一项都等于前两项之和。

递推算法

function my_recursive($des){
 if($des == 1 || $des == 2) return 1;
 $f[1] = 1;
 $f[2] = 1;
 for($i = 3;$i <= $des;$i++){
 $f[$i] = $f[$i-1] + $f[$i-2];
 }
 return $f[$des];
}

递归算法

function recursive($n){
 // 递归出口
 if($n == 1 || $n == 2) return 1;
 // 递归点
 return recursive($n-1) + recursive($n-2);
}