斐波那契数列递归算法优化

递归一用不慎容易引起性能问题，导致资源过度浪费，甚至死机。

常规实现方式：

<?php

class Test
{
    public $obj;
    public $i;
    
    public function getFB($n){
      if($n == 1 || $n == 2){
          $this->obj[$n] = 1;
          return 1;
        }else {
          $this->obj[$n] = $this->getFB($n-1) + $this->getFB($n-2);
          return $this->obj[$n];
        }
    }
}

$Test = new Test();
var_dump($Test->getFB(30), $Test->i);

注意传入值是30，更大值已经承受不住，输出结果：

int(832040)
int(1664079)

优化后算法：

<?php

class Test
{
    public $i = 0;//声明一个变量i,记录调用getFB这个函数的次数.
    
    public $obj = [];//声明一个对象obj,用来保存已经求过的项.
	
    public function getFB($n){
      $this->i++;
      //求n位是多少,就先去obj里面看看,之前求过没有,如果之前求过,就直接取出来使用.
      if(isset($this->obj[$n])){
        //如果进到了这里,说明当前这个n位已经求过,已经存进obj里面了
        return $this->obj[$n];
      }else {
        //如果进到这里来了,就说明当前这个n位之前没求过,没求过就求呗.
        if($n == 1 || $n == 2){
          $this->obj[$n] = 1;
          return 1;
        }else {
          $this->obj[$n] = $this->getFB($n-1) + $this->getFB($n-2);
          return $this->obj[$n];
        }
      }
    }
	
}

$Test = new Test();
var_dump($Test->getFB(60), $Test->i);

注意是传入值是60，轻轻松松，输出结果：

int(1548008755920)
int(117)

转载请注明：微刻 blog.wecot.cn » 斐波那契数列递归算法优化