斐波那契数列 递归

Question

斐波那契数列

// 0,1,1,2,3,5,8

function xxoo($n) {
    if($n <= 0) {
        return 0;
    } elseif($n > 0 && $n <= 2) {
        return 1;
    } else {
        return xxoo($n - 1) + xxoo($n - 2);
    }
}

echo xxoo(5); // 5

递归是怎么处理的? 不解

Answer 1

(1)当为$n=5 执行 return xxoo(4) + xxoo(3);
(2)先处理xxoo(4) return xxoo(3) + xxoo(2);
    <1>先处理xxoo(3); return xxoo(2) + xxoo(1);  1+1=2
    <2>在处理xxoo(2); return xxoo(1) + xxoo(0);  1+0=1
    <3>xxoo(4)取得最后结果2+1=3
(3)再处理xxoo(3); return xxoo(2) + xxoo(1); 1+1=2 xxoo(4)取得最后结果2
(4)xxoo(5)取得最后结果3+2=5
    

我是这么理解的，递归就是第一次调用时，在满足方法条件的情况，不停的调用同一个方法，一直到不满足调用的结果为止，然后处理数据的时候，从最后一次调用得到的结果再一层一层的往上合并得到最后的结果。

Answer 2

递归的内部原理是栈，你可把递归想象成一对括号，当递归开始相当于将前一半括号入栈，当递归调用完成后之后在出栈，这样就完成了一次递归，一次类推不停的进行进栈出栈，在进栈的时候好保存了一些额外的信息，用于还原到上一次执行此次操作的地方，以便执行后续代码，栈的大小在一般大小为1M，当递归不当超出了分配的大小，会出现一个很熟悉的错误：StackOverFlow，堆栈溢出。
有兴趣可以看看我写的文章，比较简单，可以作为一个初步的了解：
数据结构基础：栈

Answer 3

你想要得到什么结果呢，第n个斐波那契数是什么，还是前n个斐波那契数的和呢？还是想了解递归的原理呢？