python - 将递归函数转换为for循环和while循环

Question

我需要转换

def aRecursive(n):
    if n is 1:
        return 3
    else:
        return 2 * aRecursive(n-1) + 5

分为 for 循环和 while 循环。我似乎无法全神贯注于这个过程。这些循环的原始函数是:

a(1) = 3
a(n) = 2 * a(n-1) + 5

答案和解释会有很大帮助。

Answer 1

我将提供一个基于函数调用方式的解决方案。该解决方案是通用的，因为您可以使用相同的方法将任何递归函数转换为迭代函数。理论上是可能的，但似乎没有人谈论如何实现。由于您的函数很简单，因此想出一个迭代函数并不难。但是二叉树的非递归后序遍历怎么样？如果您没有我将介绍的通用方法，您只能根据具体情况进行操作。

我们开始吧。首先，我们需要写下您的递归版本，并稍加更改以方便转换:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        return 3
    else:
        return 2 * f(n-1) + 5

接下来我们将转换两件事:函数调用和返回语句。函数调用基本上分为两个步骤:将参数和返回地址压入堆栈并跳转到实际代码。 返回基本上是弹出参数并跳转到保存的地址。那么我们开始吧:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        return 3
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function
        return 2 * f(n-1) + 5  # we will never reach here... this line is where we need to return when any `return` statements is met

接下来我们将更改第一个 return 语句(return 3):

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        # for `return` we need to see if this is the top level or a inner recursive call
        if stack is empty: # we are in top level
            return res
        # hey we are in a recursive call, and we need to return to the code after `goto`, why not move these code here?
        else:
            n = pop()      # we pop the parameter saved
            # this line is where we need to return when any `return` statements is met
            return 2 * f(n-1) + 5
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function

然后我们将转换返回2*f(n-1)+5:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        if stack is empty:
            return res
        else:
            [loop]:
            n = pop()      # we pop the parameter saved
            # begin conversion of return
            res = 2*res+5
            if stack is empty:
                return res;
            else:
                # we need to pop stack and jump to the same return, so we just jump to [loop]
                goto [loop]
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function

现在转换已经完成，我们需要简化这个困惑。首先我们应该考虑是否真的需要堆栈。对于这个特定问题，每次推送都会生成 n=n-1，每次弹出都会生成 n=n+1。所以实际上并不需要堆栈。

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        if n == N:         # SAME as stack is empty
            return res     # really return
        else:
            [loop]:
            n = n+1       # WE JUST INCREASE N INSTEAD OF POP
            res = 2*res+5
            if n==N:      # SAME as stack is empty
                return res;
            else:
                goto [loop]
    else:
        # NO PUSH NEEDED
        n = n-1       # the next level actual parameter is now n-1
        goto [start]

堆栈被消除了，我们需要让这些goto语句消失。请注意 [start] 标签和 goto [start] 构成了一个循环，我们只需将它们设为“while”循环即可:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
    # we reverse the if n==1 and make it a condition in while
    while n != 1:
        # NO PUSH NEEDED
        n = n-1       # the next level actual parameter is now n-1
    # you soon noticed the above calculation is not needed at all, it just sets n = 1

    res = 3
    if n == N:
        return res
    else:
        [loop]:
        n = n+1
        res = 2*res+5
        if n==N:
            return res;
        else:
            goto [loop]

我们优化了第一个循环并将其替换为 n=1。我们需要使 [loop] 和 goto [loop] 标记的第二个循环消失:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
    n = 1        # the result of the first while loop

    res = 3
    if n == N:
        return res
    else:
        do:              # Python does not have do while, but it is straight forward to do this convert
            n = n+1
            res = 2*res+5
        while n!=N
        return res

我们很快就会注意到前 4 条语句可以合并，并且我们删除所有评论:

def f(N):
    n = 1
    res = 3
    if n == N:
        return res
    else:
        do:
            n = n+1
            res = 2*res+5
        while n!=N
        return res

我们将反转 if n==N 语句:

def f(N):
    n = 1
    res = 3
    if n != N:
        do:
            n = n+1
            res = 2*res+5
        while n!=N
        return res
    else:
        return res

很明显，return res 可以放在顶层，if n!=N 和 do/while 循环可以放在顶层。组合成一个 while 循环:

def f(N):
    n = 1
    res = 3
    while n != N:
        n = n+1
        res = 2*res+5
    return res

这是原始递归函数的等效版本。请注意，我没有深入研究这个特定问题来提出这个版本，我只处理函数调用转换。我建议您在自己喜欢的文本编辑器中自行完成整个过程，这很有趣。你会发现它非常机械，唯一需要考虑的是堆栈的使用。其他技术，如“反转 if 条件”或“将 goto 转换为结构循环”非常简单。

有趣的是，迭代版本比仅基于转换过程的递归版本更高效，因为: 1. 我们消除了堆栈的使用； 2.我们消除了将n减少到1的循环。我们至少节省了一些CPU周期和堆栈存储。