《算法图解》学习记录_chapter3（递归）
Chapter3 递归
本章内容：
✔️学习递归
✔️学习如何将问题分成基线条件和递归条件
1. 递归：
问题：假设你在祖母的阁楼中翻箱倒柜，发现了一个上锁的神秘手提箱。祖母告诉你，钥匙很可能在下面这个盒子里。这个盒子里有盒子，而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙，你将使用什么算法?
方法1（while循环）
(1) 创建一个要查找的盒子堆。
(2) 从盒子堆取出一个盒子，在里面找。
(3) 如果找到的是盒子，就将其加入盒子堆中，以便以后再查找。
(4) 如果找到钥匙，则大功告成!
(5) 回到第二步。
# 伪代码：
def look_for_key(main_box):
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
box = pile.grab_a_box()
for item in box:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print "found the key!"
方法2（递归——函数调用自己）
(1) 检查盒子中的每样东西。
(2) 如果是盒子，就回到第一步。
(3) 如果是钥匙，就大功告成!
# 伪代码
def look_for_key(box):
for item in box:
if item.is_a_box():
look_for_key(item) # 递归！
elif item.is_a_key():
print "found the key!"
“如果使用循环，程序的性能可能更高；如果使用递归，程序可能
更容易理解。如何选择要看什么对你来说更重要。”
—— byLeigh Caldwell
2. 基线条件和递归条件
由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致
无限循环。
示例：
""" 倒计时函数 """
def cutdown(i):
print(i)
cutdown(i-1)
print(cutdown(3))
# 无限循环直到报错
# RecursionError: maximum recursion depth exceeded while calling a Python object
编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。
修改后的示例：
""" 修改后倒计时函数 """
def cutdown(i):
print(i)
if i <= 0: # 基线条件
return
else: # 递归条件
cutdown(i-1)
print(cutdown(3))
3. 栈：
接下来将介绍一种重要的编程概念——调用栈（call stack）
假设你去野外烧烤，并为此创建了一个待办事项清单：一叠便条。
本书之前讨论数组和链表时，也有一个待办事项清单。在那个待办清单中，你可将待办事项添加到清单的任何地方，还可删除任何一个待办事项。
而一叠便条要简单得多：插入的待办事项放在清单的最前面；读取待办事项时，你只读取最上面的那个，并将其删除。因此这个待办事项清单只有两种操作:压入(插入)和弹出(删除并读取)。
如何使用这个待办事项清单？
我们将这种数据结构称为栈（stack）。
- 调用栈：
计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。
代码示例：
# 问候用户
def greet(name):
print("Hello, " + name + "!")
greet2(name)
print("getting ready to say bye")
bye()
def greet2(name):
print("How are you: " + name + "?")
def bye():
print("Ok bye!")
greet("maggie")
#在Python中，print是一个函数，但出于简化考虑，这里假设它不是函数。
下面详细介绍调用函数时发生的情况。
- 调用greet(“maggie”)时，计算机将首先为该函数调用分配一块内存。
2）我们使用这些内存：变量name被设置为maggie，这需要存储到内存中。（每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。）
3）接下来， 你打印”hello, maggie!“，再调用greet2(“maggie”)。同样，计算机也为这个函数调用分配一块内存。
4）计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。你打印“how are you, maggie?”，然后从函数调用返回。此时，栈顶的内存块被弹出。
5）现在，栈顶的内存块是函数greet的，这意味着你返回到了函数greet。当你调用函数greet2 时，函数greet只执行了一部分。这是本节的一个重要概念：调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet2后，你回到函数 greet，并从离开的地方开始接着往下执行：首先打印"getting ready to say bye…"，再调用函数bye。
6)在栈顶添加了函数bye的内存块。然后，你打印"ok bye!"，并从这个函数返回。
7)现在你又回到了函数greet。由于没有别的事情要做，你就从函数greet返回。
这个栈用于存储多个函数的变量，被称为调用栈。
下面让我们来康康递归函数的调用栈 : )
- 递归调用栈：
代码示例：
# 计算阶乘的递归函数
def factorial(x):
if x == 1:
return 1
else:
return(x * factorial(x-1))
下面让我们来详细分析调用递归函数factorial(3)时，调用栈是如何变化的。别忘了，栈顶的方框指出了当前执行到了什么地方。
注意：每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。
栈在递归中扮演着重要角色。
在本章开头的示例中，有两种寻找钥匙的方法。
方法一：while循环
使用这种方法时，你创建一个待查找的盒子堆，因此你始终知道还有哪些盒子需要查找。
方法二：递归
使用递归方法时，没有盒子堆。既然没有盒子堆，那算法怎么知道还有哪些盒子需要查找呢?下面是一个例子。
此时，调用栈类似于下面这样。
原来“盒子堆”存储在了栈中！这个栈包含未完成的函数调用，每个函数调用都包含还未检 查完的盒子。使用栈很方便，因为你无需自己跟踪盒子堆——栈替你这样做了。
使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择：
- 重新编写代码，转而使用循环。
- 使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言都支持尾递归。
Q：假设你编写了一个递归函数，但不小心导致它没完没了地运行。正如你看到的，对于每次函数调用，计算机都将为其在栈中分配内存。递归函数没完没了地运行时，将给栈带来什么影响?
A：栈将不断地增大。每个程序可使用的调用栈空间都有限，程序用完这些空间(终将如此)后，将因栈溢出而终止。
@ 小结：
- 递归指的是调用自己的函数。
- 每个递归函数都有两个条件：基线条件和递归条件。
- 栈有两种操作:压入和弹出。
- 所有函数调用都进入调用栈。
- 调用栈可能很长，这将占用大量的内存。