<?php 
/** 
 * 斐波那契数列
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契	数列的第n项（从0开始，第0项为0）。
	n<=39
 */

/** 
 * [Fibonacci description]
 * 递归
 */
function Fibonacci($n)
{
    if ($n == 0) {
    	return 0;
    }
    if ($n == 1) {
    	return 1;
    }
    return Fibonacci($n - 1) + Fibonacci($n - 2);
}

/**
 * 非递归 
 */
function Fibonacci1($n)
{
    $a = 0;
    $b = 1;
    while ((--$n) > 0) {
    	$t = $b;
    	$b = $a + $b;
    	$a = $t;
    }
    return $b;
}


echo Fibonacci(5);
echo "<br />";
echo Fibonacci1(5);