Python数据结构与算法27：递归：递归调用的实现

注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为4分钟。

上节说过，递归和栈这种数据结构是有关系的。本节就讨论两者具体有何关系，以及递归调用的实现过程具体是怎样的。

递归的调用过程

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈。所谓现场数据，是指包括了要返回的函数的名称、参数、局部变量等。

每次调用，压入栈的现场数据称为栈帧。当函数返回时要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回。

以上一节我们写过的任意进制转换的函数toStr(n, base)为例，给予具体参数来说明递归调用的过程。

# 将十进制整数转换为其它进制的整数。
def toStr(n, base):  
    '''
    n：int类型，十进制整数。
    base：要转换的进制基。
    '''
    convertString = "0123456789ABCDEF"
    if n < base:
        return convertString[n]
    else:
        return toStr(n // base, base) + convertString[n % base]

print(toStr(10, 2))

<<<1010

其递归的过程如下图所示：

Pic-403-1 函数toStr(10, 2)递归调用的示意图

注意，在Pic-403-1 函数toStr(10, 2)递归调用的示意图中，最上面的数字是最先入栈的，在栈底；依次往下，最下面的数字是最后入栈的，在栈顶。弹出时，先从图中最下面的数字开始，依次往上，直到图中最上面的数字被弹出。

Python中的递归深度限制

在调试递归算法程序的时候，经常会碰到这样的错误：RecursionError。这是因为递归的层数太多，系统调用栈的容量有限。

获取和调整本地计算机的递归深度限制可以用Python的sys模块。

import sys

sys.getrecursionlimit()  #获取本地计算机的递归深度限制。
Out[5]: 3000

sys.setrecursionlimit(3000)  #调整本地计算机的递归深度限制。

To be continued.