栈帧：实现递归

假设不拼接递归调用 toStr 的结果和 convertString 的查找结果，而是在进行递归调用之前把字符串压入栈中。代码清单4-4 展示了修改后的实现。

代码清单4-4 把字符串压入栈中
from pythonds.basic import Stack

rStack = Stack()

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    if n < base:
        rStack.push(convertString[n])
    else:
        rStack.push(convertString[n % base])
        toStr(n // base, base)

每一次调用 toStr，都将一个字符压入栈中。回到之前的例子，可以发现在第四次调用 toStr 之后，栈中内容如图4-5 所示。因此，只需执行出栈操作和拼接操作，就能得到最终结果 "1010"。

image 2023 12 13 11 06 22 473
Figure 1. 图4-5 栈中内容

这个例子展示了 Python 如何实现递归函数调用。当调用函数时，Python 分配一个栈帧来处理该函数的局部变量。当函数返回时，返回值就在栈的顶端，以供调用者访问。图4-6 展示了返回语句之后的调用栈。

image 2023 12 13 11 08 31 118
Figure 2. 图4-6 调用栈示例

注意，调用 toStr(2//2, 2) 将返回值 "1" 放在栈的顶端。之后，这个返回值被用来替换对应的函数调用（toStr(1, 2)）并生成表达式 "1" + convertString[2%2]。这一表达式会将字符串 "10" 留在栈顶。通过这种方法，Python 的调用栈取代了代码清单4-4 显式使用的栈。在计算一列数之和的例子中，可以认为栈中的返回值取代了累加变量。

栈帧限定了函数所用变量的作用域。尽管反复调用相同的函数，但是每一次调用都会为函数的局部变量创建新的作用域。

如果记住栈的这种思想，就会发现递归函数写起来很容易。