递归说大白话就是函数自己调用自己。递归可以帮助我们写一些很酷炫的代码。

我们先来实现一个斐波那契数列的函数，即给定一个位数，返回这个位数的斐波那契数。

如果读者不知道什么是斐波那契数列，参考斐波那契数列_百度百科。这里简单介绍，所谓斐波那契数列，就是一连串数，第一位是 1，第二位也是 1，后面所有位的值都是前两位之和，例如第三位就是第一位加第二位，也就 1+1=2，第四位就是第二位加第三位，就是 1+2=3，第五位就是第三位加第四位，就是 2+3=5，以此类推。

/**
 * 计算斐波那契数列的第n个数。
 * @param {number} n - 斐波那契数列中的位置（从1开始计数）。
 * @returns {number} 在斐波那契数列中的第n个数。
 */
function Fibonacci(n) {
    // 当n为1或2时，直接返回1，这是斐波那契数列的前两个数。
    if (n == 1 || n == 2) {
        return 1;
    }
    n -= 2; // 由于上面直接返回了前两个数，所以这里将n减去2，开始计算真正的斐波那契数列。
    var before = 1; // 初始化前一个数为1
    var after = 1; // 初始化当前数为1
    var temp; // 用于交换变量的临时变量
    // 循环n次，计算出第n个斐波那契数。
    while (n > 0) {
        temp = after; // 保存当前数
        after = before + after; // 计算下一个斐波那契数
        before = temp; // 更新前一个数
        n--; // n减1，直到计算完第n个数
    }
    return after; // 返回第n个斐波那契数
}

这里希望读者能自行写出这个代码，这个代码难度并不算高。但我们知道，任何一位斐波那契数列其实都是前面两位加上前面一位，我们利用这种递推的性质，就可以写出下面这种很简单的代码。

/**
 * 计算斐波那契数列的第n个数。
 * 
 * @param {number} n - 斐波那契数列中的位置（从1开始计数）。
 * @returns {number} 在斐波那契数列中的第n个数。
 */
function Fibonacci(n) {
    // 当n为1或2时，直接返回1，这是斐波那契数列的前两个数。
    if (n == 1 || n == 2) {
        return 1;
    }
    // 递归调用，计算第n个数，它是前两个数之和。
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

可以看到，这个函数用于计算斐波那契数列的第 n 项，如果输入的是 1 或者 2，那么固定为 1，如果不是，那这一项就应该是前一项斐波那契数列加上前两项的斐波那契数列，此时我们要获取前面两项的斐波那契数列，但不要忘了我们函数本身就是用来求斐波那契数列的，所以可以直接像上面这样写，上面这种在函数内部调用自身的函数，就称为递归函数。只要是可以写成递推公式的函数，均可用递归很轻松实现。

接下来再看一个例子，就是阶乘，我们知道，0 的阶乘和 1 的阶乘都是 1，而如果是 n 的阶乘，只要 n 大于 1，就等于 n-1 的阶乘乘以 n，我们同样可以利用这样的递推关系构造出递归函数。

/**
 * 计算给定数的阶乘。
 * 
 * @param {number} n - 要计算阶乘的非负整数。
 * @returns {number} n的阶乘结果。如果n为0或1，则返回1。
 */
function factorial(n) {
    // 当n为0或1时，直接返回1，作为递归的终止条件
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归调用，计算n-1的阶乘，并乘以n
    return n * factorial(n - 1);
}

我们借助这个函数，帮助读者分析以下递归调用的过程，我们假设调用 factorial(4)，此时由于 n 是 4，所以会返回 4*factorial(3) 的值，而 factorial(3) 会返回 3*factorial(2) 的值，相当于 factorial(4) 会返回 4*3*factorial(2) 的值，而 factorial(2) 的返回值为 2*factorial(1)，而 factorial(1) 会返回 1，故 factorial(2) 返回 2*1=2，即 factorial(4) 最终返回 4*3*2*1。

接下来深度剖析一下递归代码的执行原理，要讲清楚这个，首先要搞清楚函数调用栈。栈是一种数据结构，这种数据结构只从一侧进入，也只能从一侧出去。下面画图来理解函数的执行过程。

function B(){
	var a = 2;
	console.log(a);
}
function A(){
	var a = 1;
	B();
	console.log(a);
}
console.log("test");
A();

我们来分析上面的代码

任何一个代码都是放在全局环境下执行的，如下所示


接下来运行到 console.log("test")，此时就会执行 console.log() 函数，每当执行一个函数，函数调用栈的顶部就会添加一个项


由于程序始终只会执行函数调用栈顶部的代码，所以当 console.log() 执行结束之后，函数调用栈的顶部就应该退出，以保证全局代码往后执行。


然后执行到 A();，此时执行了一个函数，所以函数调用栈增加一项，用于执行函数 A。


执行函数 A 的时候，函数 A 内创建了一个变量 a，此时这个变量就是创建在函数调用栈的顶层的，如下图所示


此时函数 A 调用了函数 B，又会在函数调用栈中加入一项，用于执行函数 B，由于 JS 只会执行函数调用栈顶部的代码，所以 A 相当于被暂停了。


此时在 B 中创建了一个变量 a，值为 2，根据我们前面的说法，var 创建的变量实际上都是创建在函数调用栈最顶层的，如下图所示


此时函数 B 执行了 console.log(a)，这个 a 是一个变量，JS 在找变量的时候会从函数调用栈中，由上往下去找，可以看到，B 这一层就有变量 a，所以就用 B 这一层的变量 a，即最终执行的是 console.log(2) 函数，又会在顶部加上一项


console. log 执行完毕之后，退出函数执行栈，B 继续执行，但此时函数 B 也执行完毕，所以也退出函数执行栈


此时 A 继续执行，开始执行 console.log(a)，此时在当前环境下，a 的值从上往下依次找，找到的第一层就是 a=1，所以实际执行 console.log(1)，又一次入栈加出栈。



此时函数 A 执行完毕，出栈。


此时所有代码执行完毕，代码结束。这就是函数调用栈的执行过程。

接下来我们给予上面的函数调用栈，分析一下以下代码：

/**
 * 计算给定数的阶乘。
 * 
 * @param {number} n - 要计算阶乘的非负整数。
 * @returns {number} n的阶乘结果。如果n为0或1，则返回1。
 */
function factorial(n) {
    // 当n为0或1时，直接返回1，作为递归的终止条件
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归调用，计算n-1的阶乘，并乘以n
    return n * factorial(n - 1);
}

我们分析 factorial(3)

首先，调用 factorial(3)


开始执行，发现该函数返回值为 3 * factorial(2)，此时执行 factorial(2)


执行 factorial(2)，发现 factorial(2)=2*factorial(2)


此时执行 factorial(1)，发现 factorial(1) 直接返回 1，所以层层向上返回



所以最终返回的结果就是 6，这就是函数调用栈的执行过程，也就是递归的原理。

在使用递归的时候，一定注意不要忘记终止条件。如果没有终止条件，递归会无限调用自身，我们知道，调用一次就会加一层，但执行栈并不是无穷无尽的，当装不下的时候就会导致栈溢出，从而报错，这一点和死循环不一样，死循环其实并不会导致栈溢出。

如果一个函数最后一条语句是调用自身，并且这个调用自身不是表达式的一部分，就称为尾递归。如果一个函数最后一条语句是调用另一个函数，并且不是表达式的一部分，称为尾调用。某些语言或环境会对尾递归和尾调用进行优化。
在实际应用中，使用到递归的场景较少，但有时候却能大大减少思考难度。