《图解算法》第3章 递归

第3章 递归

递归

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

• 很多算法都使用了递归，因此理解这种概念很重要

基线条件和递归条件

每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用 用自己，从而避免形成无限循环

• 我们来给函数countdown添加基线条件

栈

调用栈

一个重要的编程概念——调用栈（call stack）。调用栈不仅对编程来说很重要，使用递归时也必须理解这个概念 wnymwq调用greet("maggie")，计算机将首先为该函数调用分配一块内存

变量name被设置为Maggie，这需要存储到内存中。每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值 存储到内存中

接下来，你打印hello，maggie!，再调用greet2("maggie")。同样，计算机也为这个函数调用分配一块内存

计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。你打印how are you，maggie?，然后从函数调用返回。此时，栈顶的内存块被弹出

现在，栈顶的内存块是函数greet的，这意味着你返回到了函数greet。当你调用函数greet2时，函数greet只执行了一部分。这是本节的一个重要概念：调用另一个函数时，当前函数暂停并处于未完成状态

栈用于存储多个函数的变量，被称为调用栈

递归调用栈

递归函数也使用调用栈！来看看递归函数factorial的调用栈！

每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量

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

1. 重新编写代码，转而使用循环
2. 使用尾递归。这是一个高级递归主题，不在本书讨论范围内