递归

递归是当在一定条件下时，循环调用自身的算法，因此问题也分成基线条件和递归条件。

🤔🤔🤔 案例
比如有一个箱子，打开之后有多个盒子，盒子里面又有盒子。而金币就在某一个盒子中。如果遇到这种情景，你会使用什么方法？？？

第一种方法：

使用循环，从盒子中取出一个盒子，在里面找，如果还是盒子，则放到盒子堆里面，一遍下次循环查找；如果是金币则成功！

第二种方法：

函数调用自己

javascript

// 伪代码
function find (box) {
    box.forEach(item => {
        if(item.isBox()) {
            find(box)
        } else if(item.isGold()) {
            console.log('我找到金币啦')
        }
    })
}

TIP

“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

WARNING

注意：递归函数调用自己，因此很容易会导致无限循环。

基线条件：函数不再调用自己，即跳出循环的条件。如案例的 item.isGold()

递归条件：函数调用自己的条件。如案例的 item.isBox()

基本递归就讲完了，其实递归算法还是比较简单的，最重要的是分清两种条件，而且基线条件必须是在某一个点上会发生的，不能是一个永远不会触发的条件。

🖥️ 而递归在计算机的运行机制——调用栈。

调用栈

前置知识 👉🏻 《栈和队列》

举例

javascript

function greet(name) {
    console.log('去哪呀？', name)
}

function sayBye() {
    console.log('我有事，我先走啦')
}

function sayHi(name) {
    console.log('hi, ', name)
    greet(name)
	sayBye()
}

sayHi('至安')

// 首先压入 sayHi，打印 “hi, 至安”;
// 然后执行到greet(name)，压入greet('至安')，打印 “去哪呀？至安”，执行完毕弹出 greet。
// 然后执行到sayBye，压入 sayBye，打印 “我有事，我先走啦”，执行完毕弹出 sayBye。
// 然后继续执行 sayHi，执行完毕，弹出 sayHi

而递归的调用栈就是压入和弹出栈的过程，每触发一次递归条件则压入栈的过程，而触发基线条件则就是弹出栈的过程。

因此也说明了如果没有基线条件，一直触发递归条件则一直入栈，栈最终会爆掉，程序也挂了。

TIP

其实刚开始的找金币的两种方法，原理上都是一样的，第一种方法的盒子堆就相当于第二种方法的栈，只是一种我们来跟踪，一种栈帮我们做了。

注意：使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。因此需要自己去衡量使用。

递归 ​

调用栈 ​

递归

调用栈