递归

线性递归

数组求和

const sum = (arr, length) => {
    if (1 > length) {
        return 0
    }
    return sum(arr,length-1) + arr[length-1]
}

由此实例， 可以看出保证递归算法有穷性的基本技巧： 首先判断并处理n = 0之类的平凡情
况，以免因无限递归而导致系统溢出。这类平凡情况统称“递归基”（base case of recursion） 。
平凡情况可能有多种，但至少要有一种（比如此处） ，且迟早必然会出现。

线性递归

每一递归实例对自身的调用至多一次。于是，每一层次上至多只有一个实例，且它们构成一个线性的次序关系。此类递归模式称作“线性递归”，这是递归最基本形式。

减而治之

递归每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。

递归分析

递归跟踪

将递归算法的执行过程整理为图的形式

• 算法的每一递归实例都表示为一个方框，其中注明了该实例调用的参数
• 若实例M调用实例N，则在M与N对应的方框之间添加一条有向联线

首先对参数n进行调用，再转向对参数n - 1的调用，再转向对参数n - 2的调用， …，直至最终的参数0。在抵达递归基后不再递归，而是将平凡的解（长度为0数组的总和0）返回给对参数1的调用；累加上A[0]之后，再返回给对参数2的调用；累加上A[1]之后，继续返回给对参数3的调用； …；如此依次返回，直到最终返回给对参数n的调用，此时，只需累加A[n - 1]即得到整个数组的总和。

递归方程

通过对递归模式的数学归纳，导出复杂度定界函数的递推方程组及其边界条件，从而将复杂度的分析， 转化为递归方程组的求解

（使用求导函数来得到该递推方程）

递归模式

多递归基

为保证有穷性，递归算法都必须设置递归基，且确保总能执行到。 为此，针对每一类可能出现的平凡情况，都需设置对应的递归基， 故同一算法的递归基可能（显式或隐式地）不止一个。

实现递归

在设计递归算法时， 往往需要从多个角度反复尝试， 方能确定对问题的输入及其规模的最佳
划分方式。有时，还可能需要从不同的角度重新定义和描述原问题，使得经分解所得的子问题与
原问题具有相同的语义形式。

多向递归

递归消除

空间成本

较之同一算法的迭代版，递归版往往需耗费更多空间，并进而影响实际的运行 速度。另外， 就操作系统而言，为实现递归调用需要花费大量额外的时间以创建、维护和销毁各 递归实例，这些也会令计算的负担雪上加霜。有鉴于此，在对运行速度要求极高、存储空间需精 打细算的场合，往往应将递归算法改写成等价的非递归版本。

尾递归及其消除

在线性递归算法中，若递归调用在递归实例中恰好以最后一步操作的形式出现，则称作尾递归。实际上， 属于尾递归形式的算法，均可以简捷地转换为等效的迭代版本。
请注意，尾递归的判断应依据对算法实际执行过程的分析，而不仅仅是算法外在的语法形式。
比如，递归语句出现在代码体的最后一行， 并不见得就是尾递归；严格地说，只有当该算法（除
平凡递归基外）任一实例都终止于这一递归调用时，才属于尾递归。比如数组求和就不是尾递归。（实质的最后一次 操作是加法运算）

二分递归

分而治之

凡治众如治寡，分数是也

要求对原问题重新表述，以保证子问题与原问题在接口形式上 的一致。
既然每一递归实例都可能做多次递归，故称作“多路递归”（multi-way recursion） 。 通常都是将原问题一分为二，故称作“二分递归” （binary recursion）。需强调的是，无论 是分解为两个还是更大常数个子问题，对算法总体的渐进复杂度并无实质影响。

数组求和

效率

并非所有问题都适宜于采用分治策略。实际上除了递归，此类算法的计算消耗主要来
自两个方面。首先是子问题划分，即把原问题分解为形式相同、规模更小的多个子问题，比如代
码1.11中sum()算法将待求和数组分为前、后两段。其次是子解答合并，即由递归所得子问题的
解，得到原问题的整体解，比如由子数组之和累加得到整个数组之和。
为使分治策略真正有效,不仅必须保证以上两方面的计算都能高效地实现，还必须保证子问
题之间相互独立各子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。否则，
或者子问题之间必须传递数据，或者子问题之间需要相互调用，无论如何都会导致时间和空间复
杂度的无谓增加。

Fibonacci数：二分递归

// 第n项
const fib = (n) => {
    return n<2 ? n : fib(n-1)+fib(n-2)
}
/** 
 * 然而不幸的是，在这种场合采用二分递归策略的效率极其低下。实际上,该算法需要运行指数型的时间才能
计算出第n个Fibonacci数。
*/

是因为计算过程中所出现的递归实例重复度极高
子问题fib(n-1) 和fib(n-2)实际上并非彼此独立。

优化策略

为消除递归算法中重复的递归实例， 一种自然而然的思路和技巧，可以概括为：
借助一定量的辅助空间， 在各子问题求解之后，及时记录下其对应的解答
比如，可以从原问题出发自顶而下，每当遇到一个子问题，都首先查验它是否已经计算过， 以期通过直接调阅记录获得解答，从而避免重新计算。 也可以从递归基出发，自底而上递推地得 出各子问题的解，直至最终原问题的解。前者即所谓的制表（tabulation）或记忆（memoization）
策略，后者即所谓的动态规划（dynamic programming） 策略。

Fibonacci数：线性递归

Fibonacci数： 迭代

使用动态规划