JavaScript函数之递归

JS函数

从本篇文章开始，我们将继续回到JavaScript函数的学习。在学JS基础时我们初步学习了函数，讲解了函数的定义，函数调用，函数参数等问题。这里就不再重述函数基础了，有需要的读者可以翻阅JavaScript函数。在函数进阶中，我们将学习到递归堆栈，函数作用域，立即执行函数，闭包，构造函数，回调函数，this关键字，call、apply执行上下文，箭头函数等内容。

递归思想

递归是一种编程模式，在一个任务可以自然地拆分成多个相同类型但更简单的任务的情况下非常有用。或者，在一个任务可以简化为一个简单的行为加上该任务的一个更简单的变体的时候可以使用。或者，就像我们很快会看到的那样，处理某些数据结构。当一个函数解决一个任务时，在解决的过程中它可以调用很多其它函数。在部分情况下，函数会调用 自身。这就是所谓的 递归。

说的有点抽象，我们举个例子就比较清晰。比如我们要计算1到10的和，使用递归来来计算就特别的简单。现在我们使用两种方法来实现这个例子：使用循环语句和使用递归。

使用for循环我们可以累加1至10的和：

function add(n) {
    let result = 0;
    for(let i = 0; i <= n; i++){
        result += i;
    }
    return result;
}
console.log(add(10));//55

//n是个自定义值，我们也可以利用这个函数计算其他数值

console.log(add(20));//210

下面我们使用递归来实现一下上面的功能：

function adds(n) {
    if(n == 1){
        return n;
    }
    return n+adds(n-1);
}

console.log(adds(10));//55
console.log(adds(20));//210

递归的原理是一个自上而下函数调用自己的执行过程，执行到一个自定义值就让这个函数递归执行。递归将函数调用简化为一个更简单的函数调用，然后再将其简化为一个更简单的函数，以此类推，直到结果变得显而易见。最重要的一点是，递归一定要设置一个跳出自调用的值，而且这个值是可控的，受制于JS引擎的影响，一般10000以内的递归都是可执行的。

正如上面的例子，循环和递归都可以计算和。实际上，任何递归函数都可以被重写为循环形式。有时这是在优化代码时需要做的。但对于大多数任务来说，递归方法足够快，并且容易编写和维护。

递归的应用场景

在我们实际学习工作中，递归算法一般用于解决三类问题：

• 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

• 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

• 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

下面我们使用递归实现一些常用的应用：

递归实现阶乘

阶乘是数学上一个常见的算法，类似于上面求和，只是把运算符改为乘法。

1*2*3*4*5*...

function multi(n) {
    if(n == 1){
        return n;
    }
    return n*multi(n-1);
}

console.log(multi(10));//3628800

斐波纳契数列

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……

function fibonacci(n) {
    if (n == 1 || n == 2) {  
        return 1;       
    }
    return fibonacci(n-1)+fibonacci(n-2);    
}

console.log(fibonacci(10));//55

汉诺塔问题

古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。 有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。

function  moveDish(level, from, inter, to) { 
    if (level == 1) { 
        console.log("从" + from + " 移动盘子" + level + " 号到" + to);
    } else {
        // 递归调用：将level-1个盘子从from移到inter(不是一次性移动，每次只能移动一个盘子,其中to用于周转)
        moveDish(level - 1, from, to, inter); // 递归调用，缩小问题的规模
        // 将第level个盘子从A座移到C座
        console.log("从" + from + " 移动盘子" + level + " 号到" + to); 
        // 递归调用：将level-1个盘子从inter移到to,from 用于周转
        moveDish(level - 1, inter, from, to); // 递归调用，缩小问题的规模
    }
}

moveDish(10,'A','B','C');

二叉树问题

二叉树是一个类似 一分二，二分四，四分为八的树状模型，二叉树的每个节点都有左右两个子节点。

二叉树的第n层有几个节点，这个问题比较简单，它的每层节点树是一个有规律的数列，类似1 2 4 8 16 32 ...，使用递归很容易求值。

function tree(n) {
    if(n==1){
        return n;
    }
    return 2*tree(n-1);
}
console.log(tree(10));//512

二叉树深度遍历问题，二叉树的深度可以通过三种方法遍历，前序，中序和后序遍历。

function preorderTraversal(root) {//前序
    let result = []
    let preorder = (root) => {
        if (root) {
            result.push(root.value)
            preorderTraversal(root.left)
            preorderTraversal(root.right)
        }
    }
    return result
};

function inorder(root) {//中序
    let result = []
    let inorder = (node) => {
        if (!node) {
            return
        }
        inorder(node.left);
        result.push(node.value);
        inorder(node.right);
    }
    inorder(root)
    return result
};

function postorder(root) {//后序
    let result = []
    let postorder = (node) => {
        if (!node) {
            return
        }
        postorder(node.left)
        postorder(node.right)
        result.push(node.value)
    }
    postorder(root)
    return result
};