我们应该遇到过很多次类似的题目了吧: 如何将一个递归函数使用非递归的方式实现.. 今天突然想到一个通用解, 就是可以在循环中模拟函数调用的方式来实现.

调用栈

以计算 1~n 的和举例, 递归实现如下(Python为例):

def add_up(n):
    if n <= 1:
        return n
    return n + add_up(n-1)

众所周知, 函数的调用时通过栈实现的, 每次调用函数的大致流程如下:

1. 将参数入栈 (还有返回时的 PC, 这里省略了)
2. 调用函数
3. 读取参数(出栈)
4. 返回结果入栈
5. 函数返回, 读取返回值(出栈)

假设调用函数add_up(4), 那么栈中的内容大致如下:

这里为了方便展示, 对栈中的数据做了简化(比如 返回地址去掉了, 前后入参拆开展示等等), 不必纠结这些细节, 只要了解大致思路即可.

当add_up(1)返回之后, 再将所有数据依次出栈得到最终结果.

模拟栈调用

好, 既然函数调用就是对栈的一系列操作, 那么回到我们最开始的问题: 如何用非递归的方式来实现递归函数. 是不是有思路了? 只要在内存中模拟函数调用的过程, 就可以将其无缝转换了.

话不多说, 直接上代码:

def add_up_by_stack(n):
    # 没必要进入递归
    if n <= 1:
        return 1
    stack = []
    down = 1  # 向下调用函数标记
    up = -1  # 函数返回标记

    # 入栈内容依次为: 局部变量, 函数参数, 函数返回值, 调用方向
    stack.append((n, n - 1, 0, down))
    while len(stack) > 0:
        # 从栈中读取上一级放入的内容
        (num, param_num, return_num, operate) = stack.pop()
        # 当前是函数调用 return 阶段, 且已经到最后一级了, 因此直接返回结果即可
        if operate is up and len(stack) == 0:
            # 结果为 当前的局部变量 + 函数返回值
            # 对应了递归中的 n + return_n
            return num + return_num
        # 开始函数调用模拟
        if operate is down:  # 调用下一级
            if param_num <= 1:  # 返回结果
                # 模拟 if n <= 1: return 1
                # 将结果返回给上一级
                stack.append((num, param_num, 1, up))
            else:
                # 模拟 return n + add_up(n-1)

                # 因为当前内容还没有调用完, 需要向下调用. 因此将当前级别放回去
                # 但是放回去时, 要将 down 改为 up, 已经到达 return 了, 下次回来直接返回
                stack.append((num, param_num, return_num, up))
                # 调用下一级, 将数据入栈
                stack.append((param_num, param_num - 1, 0, down))
        else:
            # 当前为递归返回阶段, 则需要将当前函数的返回值返回给调用方
            # 将上一层数据取出, 并将返回结果放进去
            # 对应了递归中的 n + return_n
            (last_num, last_param_num, last_return_num, last_operate) = stack.pop()
            stack.append((last_num, last_param_num, num + return_num, last_operate))
    # 不会走到这里
    raise Exception("error")

我在注释中写的很详细了, 若有看不懂的可在本地自行调试.

如何, 是不是有点意思? 其实就是将递归的函数调用过程自己实现了一次, 依照这个思路, 所有的递归函数都可以转换为非递归的方式. 至于更为复杂的调用未尝试, 在此抛砖引玉

原文地址: https://hujingnb.com/archives/886