将递归转换为尾递归

Question

我在阅读关于将递归算法转换成迭代算法的文章。我看到了一篇博客文章http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html，解释了将递归算法首先转换为尾递归算法，然后再将尾递归转换为迭代算法的过程。在文章中，解释了当我们想要将递归算法转换为尾递归算法时，应该先理解在递归调用返回和调用函数的返回语句之间发生了什么。一旦这样做了，我们应该尝试向递归函数添加一个秘密功能/累加器参数，然后决定要返回什么。我按照博客文章中给出的示例进行了操作，但是我无法解决博客结尾处给出的练习。我不知道我的累加器参数应该是什么？我该如何根据该累加器参数做出决策。我不需要解决方案，只需要指出一些指针，告诉我应该如何思考来解决这个问题。以下是练习代码：

def find_val_or_next_smallest(bst, x):
    """Get the greatest value <= x in a binary search tree.

    Returns None if no such value can be found.

"""
    if bst is None:
        return None
    elif bst.val == x:
        return x
    elif bst.val > x:
        return find_val_or_next_smallest(bst.left, x)
    else:
        right_best = find_val_or_next_smallest(bst.right, x)
        if right_best is None:
            return bst.val
        return right_best 

谢谢您的提前帮助！

- user2056245

---

@VPfB 谢谢。我会尝试并告诉你结果。 - user2056245

如果我无法解决问题，我会请求一个解决方案。 - user2056245

是的。我正在尝试存储nextSmallValue并将其传递给后续的尾递归调用。但是仍然会在某些情况下卡住。 - user2056245

你的代码不是尾递归，因为尾递归指的是在递归调用之后没有代码。 - Luai Ghunim

是的，我想将那段代码转换为尾递归。 - user2056245

@VPfB 我想与您分享我的代码，并希望看到您的解决方案。还有其他方式可以做到吗？ - user2056245

Answer 1

我发布这篇文章是为了替换昨天的评论并展示代码。

在递归算法中，每次调用都会创建一个包含函数本地变量和传递参数的堆栈帧。所有堆栈帧一起保存某种状态信息。当你要避免递归时，将不会有额外的堆栈帧。因此，重要的数据必须在非递归函数中维护。

现在来看代码。我尽力紧密地遵循了指示。

这是原始源代码。我只省略了文档字符串，并将紧接在return之后出现的elif替换为if（这只是一种偏好风格问题）。

def find_val_or_next_smallest1(bst, x):
    if bst is None:
        return None
    if bst.val == x:
        return x
    if bst.val > x:
        return find_val_or_next_smallest1(bst.left, x)
    else:
        right_best = find_val_or_next_smallest1(bst.right, x)
        if right_best is None:
            return bst.val
        return right_best

---

现在来说尾递归。有四个分支。两个非递归，一个已经是尾递归，第四个需要改写：

    right_best = find_val_or_next_smallest1(bst.right, x)
    if right_best is None:
        return bst.val
    return right_best

该分支将bst.val或调用结果中更好的那个作为结果。调用必须最后执行，因此必须将bst.val传递给它。该函数获得一个新参数，意思是“如果您找不到更好的，请返回此值”。在更改之前，它是“如果您找不到任何内容，则返回None”。因此，我们只需替换None值。我将新参数称为found，因为这是我们迄今为止发现的。

def find_val_or_next_smallest2(bst, x, found=None):
    if bst is None:
        return found
    if bst.val == x:
        return x
    if bst.val > x:
        return find_val_or_next_smallest2(bst.left, x, found)
    else:
        return find_val_or_next_smallest2(bst.right, x, found=bst.val)

---

就像博客中所述的那样，直接进行转换：

def find_val_or_next_smallest3(bst, x, found=None):
    while True:
        if bst is None:
            return found
        if bst.val == x:
            return x
        if bst.val > x:
            bst, x, found =  bst.left, x, found
        else:
            bst, x, found =  bst.right, x, bst.val

和清理：

def find_val_or_next_smallest4(bst, x):
    found=None
    while True:
        if bst is None:
            return found
        if bst.val == x:
            return x
        if bst.val > x:
            bst = bst.left
        else:
            bst, found = bst.right, bst.val

- VPfB