递归

递归是一种高效、简洁的编码技巧

满足下面三点的问题，即可用递归来解决

1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

如何编写递归代码

写出递推公式，找出终止条件，翻译成递归代码

递归代码的问题

• 有堆栈溢出风险
• 重复计算
• 函数调用耗时多
• 空间复杂度高

函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或虚拟机栈空间一般都不大，如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

问题举例

1. 假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

   思路：根据第一步的走法把所有走法分为两类，第一类是第一步走了一个台阶，第二类是第一步走了两个台阶，所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法 加上 先走2阶后，n-2个台阶的走法。
   所以递推公式就是：f(n) = f(n-1) + f(n-2)
   终止条件就是：f(1) = 1; f(2) = 2

   代码：

/**
 * 带有重复计算
 * @param $n
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;
    return f($n-1) + f($n-2);
}


// ===========


$hasSolved = [];

/**
 * 去除重复计算
 * @param $n
 * @param $hasSolved
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;

    global $hasSolved;

    if (isset($hasSolved[$n])) {
        return $hasSolved[$n];
    }

    $result = f($n-1) + f($n-2);
    $hasSolved[$n] = $result;
    return $result;
}


// ===========


/**
 * 非递归 （相当于 斐波那契数列求和）
 * $pre -> f(n-1), $prepre -> f(n-2)
 * @param $n
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;

    $result = 0;
    $pre = 2;
    $prepre = 1;

    for ($i = 3; $i < $n; $i++) {
        $result = $pre + $prepre;
        $prepre = $pre;
        $pre = $result;
    }
    
    return $result;
}