递归

小结

1. 递归指的是调用自己的函数。

2. 每个递归函数都有两个条件：基线条件和递归条件。

3. 所有函数调用都进入调用栈。

4. 栈有两种操作：压入和弹出。

5. 调用栈可能很长，这将占用大量的内存。

调用栈

递归函数用调用栈进行多次调用，当符合条件时才开始依次将一层一层调用返回。先通过一次次调用，将栈垒高，然后再从最上方一层一层地返回。整个过程有些像倒U型。

调用栈期间会持续累积调用信息，很占计算机内存。递归会持续记录调用状态，在返回条件触发之前并不会执行这些调用。这就有点像Spark里面的转换算子和行动算子，在行动之前，转换惰性调用，只记录前后的依赖关系，并不会进行计算操作。

使用栈虽然很方便，但是也要付出代价：存储详尽的调用信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。

1. 重新编写代码，转而使用循环。

2. 使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言 都支持尾递归。