JavaScript 递归

[Checkson]

前言

递归，对于我们很多人来说，并不会陌生。它很早就出现在《算法与数据结构》教科书上，并广泛应用在生产环境中。

定义

程序调用自身的编程技巧称为递归（recursion）。更具体来讲，一个函数（方法）直接调用自身，或者间接调用自身的过程，我们称之为递归。

• 优点：递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

• 缺点：递归在很多高级语言中还没得到很好的优化，使用不当或者滥用递归，很容易会让程序调用栈溢出，或者运算时间过长，甚至导致程序崩溃。

注意，递归函数必须具有终止条件，不能无限递归，这样就同等于“死循环“。

实例

1. 求解前n项正整数和

这道题的常用解法，我们可以用一个简单的循环完成。

function sum (n) {
    var res = 0;
    for (var i = 0; i <= n; i++) {
        res += i;
    }
    return res;
}

如果换成递归解法话，解法一般如下：

function sum (n) {
    if (n <= 0) {
        return 0;
    }
    return sum(n - 1) + n;
}

这种常用的递归方式叫“线性递归”。随着n的增大，调用堆栈开辟的空间会随之呈线性增长。

2. 求解斐波拉契数列第n项

斐波拉契数列的定义：当 n = 1 时，fibo(1) = 1；当 n = 2 时，fibo(2) = 1；当 n > 2 时, fibo(n) = fibo(n - 1) + fibo(n - 2)。

根据以上的定义，我们轻松写出如下用递归方式实现的代码：

function fibo (n) {
    if (n <= 1) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

细心的同学可能已经发现到，fibo 函数每一次调用，都需要递归调用自身两次或者更多次，这种递归方式，我们称为“树形递归”。随着n的增大，调用堆栈开辟的空间随之呈指数增长。

无论是线性递归还是树形递归，随着递归深度的增大，系统资源消耗都会加倍剧增。那么我们还有什么优化空间呢？

答案是：尾递归。

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

实例1中求解前n项和，最多需要保存n个调用记录，复杂度 O(n) 。那么改成尾递归，只保留一个调用记录，复杂度 O(1) 。

function sum (n, total) {
   if (n <= 0) return total;
   return sum(n - 1, n + total);;
}

尾递归优化过的 fibo 数列实现如下。

function fibo (n, a = 0, b = 1) {
    if (n <= 1) return b;
    return fibo(n - 1, b, a + b);
}

汉诺塔

提到递归，就不得不提汉诺塔问题。

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

例如我们有三个盘子需要从A柱移到C柱：

我们大概需要的步骤如下：

换成抽象步骤表达则是：

• 第一步：A ---> C
• 第二步：A ---> B
• 第三步：C ---> B
• 第四步：A ---> C
• 第五步：B ---> A
• 第六步：B ---> C
• 第七步：A ---> C

可以看出，移动的步数是：2ⁿ - 1，n >= 1。

思路

绝大部分的教科书上，都会用老和尚分工的思路来解释这个汉诺塔递归原理，过程比较臃肿。这里我总结三条原则：

• 首先，我们要借助 C 柱来将 n - 1 个盘从 A 柱移到 B 柱。
• 接着，我们将 A 柱上的第 n 号盘移到 C 柱。
• 最后，我们要借助 A 柱来将 n - 1 个盘从 B 柱移到 C 柱。

代码实现

/**
 * 汉诺塔递归解法
 * @param {number} n 盘数
 * @param {string} A A柱名称
 * @param {string} B B柱名称
 * @param {string} C C柱名称
 */
function hanoi (n, A, B, C) {
    if (n === 1) {
        move(n, A, C);
        return;
    }
    hanoi(n - 1, A, C, B);
    move(n, A, C);
    hanoi(n - 1, B, A, C);
}

/**
 * 移动圆盘
 * @param {number} n 第几号圆盘
 * @param {string} N 起始柱子编号
 * @param {string} M 结束柱子编号
 */
function move (n, N, M) {
    console.log('把第' + n + '号圆盘从 ' + N + ' 柱移到 ' + M + ' 柱');
}

分析以上代码得知，汉诺塔递归解法，也是“树形递归”的一种。

排列组合

排列组合在数学领域是非常出名的，在ACM训练题中也是常客。例如：字母ABC的全排列有：ABC、ACB、BAC、BCA、CBA、CAB。

思路

在有 n 个元素的数组中，按顺序抽取一个元素当数组的第一个元素，剩下的 n - 1 元素递归完成同样操作。

代码实现

/**
 * 排列组合递归实现
 * @param {array}  arr    待排列数组
 * @param {number} start  开始坐标
 * @param {number} end    结束坐标
 */
function permute (arr, start, end) {
    if (start === end) {
        echo(arr);
        return;
    }
    for (var i = start; i <= end; i++) {
        swap(arr, start, i);
        permute(arr, start + 1, end);
        swap(arr, start, i);
    }
}

/**
 * 输出数组排列结果
 * @param {array} arr 
 */
function echo (arr) {
    console.log(arr.join(''));
}

/**
 * 交换数组中指定坐标的两个元素的值
 * @param {*} arr 待交换值的数组
 * @param {*} i   下标i
 * @param {*} j   下标j
 */
function swap (arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

排列组合的递归实现方式，是属于“树形递归”的一种，千万别给它函数体内只有一个递归调用而被蒙骗，因为它在一个 for 循环里面。

N皇后问题

N皇后问题是指：N*N 的棋盘要摆 N 个皇后，要求任何两个皇后不同一行、不同一列、也不在同一条斜线上。给定一个正整数 n，返回 n 皇后的摆法有多少种。

思路

如果第 i 行，第 j 列放置了一个皇后，那么哪些位置不能放置皇后呢？

1. 第 i 行剩下空余的所有位置都不能放置皇后。
2. 第 j 列剩下空余的所有位置都不能放置皇后。
3. 第 a 行，第 b 列位置若与（i，j）成对角线，即满足 |a - i| = |b - j|，都不能放置皇后。

这里，我们采用的实现方式是递归回溯。递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

我们用一维数组arr来代表以找到符合条件的皇后坐标，row代表行数，arr[row]代表列数。

代码实现

/**
 * 判断坐标（row,col）是否安全
 * @param {array}  arr 
 * @param {number} row 
 * @param {number} col 
 */
function isSafe (arr, row, col) {
    for (var i = 0; i < row; i++) {
        if (col === arr[i] || Math.abs(arr[i] - col) === Math.abs(i - row)) {
            return false;
        }
    }
    return true;
}

/**
 * 寻找N皇后问题的解法数
 * @param {number} row 
 * @param {array}  arr 
 * @param {number} n 
 */
function NQueen (row, arr, n) {
    // 若所有行都被搜索完，则说明本次方案可靠！
    if (row === n) {
        return 1;
    }
    // 返回的结果
    var ans = 0;
    
    // 对于第row行，每一列都可能是皇后的摆放位置
    for (var col = 0; col < n; col++) {
        //如果该列满足条件，递归寻找下一行皇后可以摆放的位置
        if (isSafe(arr, row, col)) {
            arr[row] = col;
            ans += NQueen(row + 1, arr, n);
        }
    }

    return ans;
}

很显然，N皇后问题，也是属于“树形递归的一种”。

参考链接

• 汉诺塔的图解递归算法
• 排列组合递归和非递归算法总结篇
• N皇后问题（递归和动态规划）