php实现记忆化递归--以斐波那契数列为例（还是以边学边做为主，注重练习）

一、总结

1、递归不优化的话，30层开外就有点吃力了

2、php因为定义变量的时候不用定义变量类型，所以数组里面的类型也是php自动选择，这就会有下面的情况：

当int不够的时候自动转化为float，float不够的时候自动转化为科学计数法

二、php实现记忆化递归--以斐波那契数列为例

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

三、代码

代码一

 1 <?php
 2 
 3 $arr = array(0,1,1);
 4 for($i=3;$i<=100;$i++){$arr[$i]=-1;}
 5 function Fibonacci($n)
 6 {
 7     global $arr;
 8     if($arr[$n]!=-1) return $arr[$n]; //1、边界情况都可以结合 记忆化递归数组判断，对比一下下面的代码就知道简便之处了
 9     else{
10         $arr[$n-1]=$arr[$n-1]!=-1?$arr[$n-1]:Fibonacci($n-1);
11         $arr[$n-2]=$arr[$n-2]!=-1?$arr[$n-2]:Fibonacci($n-2);
12         return $arr[$n]=$arr[$n-1]+$arr[$n-2];
13     }
14 }

代码二

 1 <?php
 2 namespace appindexcontroller;
 3 
 4 use appindexcontrollerBase;
 5 
 6 class Exercise extends Base
 7 {
 8     public function index()
 9     {
10         $this->FibonacciDemo();
11     }
12 
13     //斐波那契数列 
14     private $arr = array();//记忆化递归数组
15     public function Fibonacci($n)
16     {
17         global $arr;
18         if($n==0) return 0;
19         else if($n==1||$n==2) return 1; //1、php中的逻辑连接符：和java一样,例如|表示位运算符，||表示逻辑运算符
20         else{
21             $arr[$n-1]=$arr[$n-1]!=-1?$arr[$n-1]:$this->Fibonacci($n-1);
22             $arr[$n-2]=$arr[$n-2]!=-1?$arr[$n-2]:$this->Fibonacci($n-2);
23             return $arr[$n]=$arr[$n-1]+$arr[$n-2]; //2、支持这样的返回方式，这应该是先赋值再返回  3、把求出的值给记录下数组，刚刚忘记记录$arr[$n]了
24         }
25     }
26     public function FibonacciDemo(){
27         global $arr;
28         for ($i=0; $i <100 ; $i++) { 
29             $arr[$i]=-1;
30         }
31         $arr[0]=0;
32         $arr[1]=1;
33         $arr[2]=1;
34         echo($this->Fibonacci(50));
35         dump($arr);die;
36     }
37 
38 }

截图：