本文参照此处实现: 递归函数转非递归(通用方法)[1/2]——数据结构 递归函数转非递归(通用方法)[2/2]

先说总结，这种方案总的来说就是机械化的强转，时间复杂度和空间复杂度没什么变化，唯二的优点可能是1. 不会爆栈，2. 节省了函数调用的开销

而且最终产出的代码效果不那么美观，比较冗长

思路是：当发生递归调用时，模拟函数调用的压栈。并处理入参和返回值和记录返回到当前栈的时候该继续从哪里执行

以如下递归(leetcode爬楼梯)为例

1
2
3
4
def f(n):
    if n <= 2:
        return n
    return f(n - 1) + f(n - 2)

第一步：

将涉及到递归调用的，单独变成最简单的一行

1
2
3
4
5
6
def f(n):
    if n <= 2:
        return n
    a = f(n - 1)
    b = f(n - 2)
    return a + b

第二步:

我们需要模拟递归栈调用，当执行完递归回到当前栈的时候需要知道从哪里继续执行，所以需要一个flag标记，开始的时候为0，我们先手工标记一下，再后序转换的时候可以方便查看

1
2
3
4
5
6
7
8
def f(n):
    if n <= 2:
        return n
    a = f(n - 1)
    # flag1
    b = f(n - 2)
    # flag2
    return a + b

第三步:

构建解题模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def f_iter(n):
    stack = []
    # 入参，接收递归调用的(a,b), flag
    base_frame = [None, {'a': None, 'b': None}, 0]
    first_frame = [(n, 'a'), {}, 0]
    stack.append(base_frame)
    stack.append(first_frame)
    while len(stack) > 1:
        arg, local, flag = stack[-1]
        arg, aorb = arg
        if flag == 0:
            pass
        elif flag == 1:
            pass
        elif flag == 2:
            pass
    return stack[0][-2]['a']

first_frame = [(n, 'a'), {}, 0]注意此时接收函数返回的时候为什么是一个字典，并且调用参数的时候传参多了一个’a’，因为函数被递归调用了两次，分别得到一个a和b, 所以在返回的时候需要知道返回是给a还是给b， 如果只递归调用了一次，那么就不需要带上’a’，返回的时候也不用是字典了，最后整个函数执行完成之后，base_frame里面就是最终的答案

第四步：

填充骨架，记住两点就可以了

  1. 函数调用的时候，先将当前栈的flag修改(等再次执行到当前栈的时候知道从哪里继续执行)
  2. 发生return 的时候stack.pop出栈后，将结果写入栈顶的结果字典

其他照抄就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def f_iter(n):
    stack = []
    # 入参，局部变量(a,b), flag
    base_frame = [None, {'a': None, 'b': None}, 0]
    first_frame = [(n, 'a'), {}, 0]
    stack.append(base_frame)
    stack.append(first_frame)
    while len(stack) > 1:
        arg, local, flag = stack[-1]
        arg, aorb = arg
        if flag == 0:
            if arg <= 2:
                stack.pop()
                stack[-1][-2][aorb] = arg
            else:
                stack[-1][-1] = 1
                new_frame = [(arg - 1, 'a'), {}, 0]
                stack.append(new_frame)
        elif flag == 1:
            stack[-1][-1] = 2
            new_frame = [(arg - 2, 'b'), {}, 0]
            stack.append(new_frame)
        elif flag == 2:
            a, b = local['a'], local['b']
            stack.pop()
            stack[-1][-2][aorb] = a + b
    return stack[0][-2]['a']

完结，撒花🎉

另外：有一些函数编程语言，能将所有的递归调用转化成尾调用(非尾递归)，这样就不会发生爆栈的问题，但是目前流行的大多数语言都是没有这个功能的

附加练习

有兴趣可以自己按步骤试一试, 如有见解，欢迎探讨👏

二叉树中序遍历

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def list2tree(l):
    if len(l) == 1:
        return Node(l[0])
    mid = (len(l) - 1) >> 1
    root = Node(l[mid])
    root.left = list2tree(l[:mid])
    root.right = list2tree(l[mid + 1:])
    return root

def inorder_recursive(root):
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

l = list(range(1, 2 << 2))
tree = list2tree(l)

c = inorder_recursive(tree)
print(c)

非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def list2tree(l):
    stack = []
    # (root, left_right), {'a':,'b':}, flag
    base_frame = [None, {}, 0]
    first_frame = [(l, 'a'), {}, 0]
    stack.append(base_frame)
    stack.append(first_frame)
    while len(stack) >1:
        cur = stack[-1]
        arg, local, flag = cur
        arg, aorb = arg
        mid = (len(arg) - 1) >> 1
        if flag == 0:
            if len(arg) == 1:
                stack.pop()
                stack[-1][-2][aorb] = Node(arg[0])
            else:
                stack[-1][-1] = 1
                new_frame = [(arg[:mid],'a'), {}, 0]
                stack.append(new_frame)
        elif flag == 1:
            stack[-1][-1] = 2
            new_frame = [(arg[mid+1:],'b'),{}, 0]
            stack.append(new_frame)
        elif flag == 2:
            left, right = local['a'], local['b']
            root = Node(arg[mid])
            root.left = left
            root.right = right
            stack.pop()
            stack[-1][-2][aorb] = root
    return stack[0][-2]['a']

def inorder_recursive(root):
    stack = []
    base_frame = [None, {}, 0]
    first_frame = [(root, 'a'), {'a': None, 'c': None}, 0]
    stack.append(base_frame)
    stack.append(first_frame)
    while len(stack) > 1:
        cur = stack[-1]
        arg, local, flag = cur
        arg, left_right = arg
        if flag == 0:
            if not arg:
                stack.pop()
                stack[-1][-2][left_right] = []
            else:
                stack[-1][-1] = 1
                new_frame = [(arg.left, 'a'), {}, 0]
                stack.append(new_frame)
        elif flag == 1:
            stack[-1][-1] = 2
            new_frame = [(arg.right, 'c'), {}, 0]
            stack.append(new_frame)
        elif flag == 2:
            b = [arg.val]
            ret = local['a'] + b + local['c']
            stack.pop()
            stack[-1][-2][left_right] = ret
    return stack[0][-2]['a']

l = list(range(1, 2 << 2))
tree = list2tree(l)

c = inorder_recursive(tree)
print(c)