斐波那契数列(fibonacci)非递归(迭代)方法的php实现

算法 admin 184℃ 0评论

以下是斐波那契数列非递归方法的php实现的代码

function foo($n){
	if($n == 0){
		return 0;
	}
	if($n == 1){
		return 1;	
	}
	$a = 0;
	$b = 1;
	$i = 2;
	$ret;
	for($i=2; $i<=$n; $i++){
		$ret = $a+$b;
		$a = $b;
		$b = $ret;
	}
	return $ret;
}

echo foo(5);

递归方法的缺点

  1. 递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。->效率
  2. 递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算,如fibonacci斐波那契数列的递归实现。->效率
  3. 调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出。->性能

所以在这种环境下,遇到递归的算法,就需要看看是否能够进行优化,转化成为迭代的解法。一般情况下,给出初始值,求给定参数的值是可以通过迭代来处理递归的,处理方法既

$ret = 0;
for(i=0; i<n; i++){
    $ret = f(i)+$ret
}

return $ret;

具体处理依据实际情况变化

转载请注明:朋克网 » 斐波那契数列(fibonacci)非递归(迭代)方法的php实现

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址