将递归转换为尾递归
我读过关于将递归算法转换为迭代算法的文章。我遇到了一个博客文章http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html，它解释了首先将递归算法转换为尾递归算法，然后将尾部递归算法转换为迭代算法的过程。在文章中，我们解释说，当我们要将递归算法转换为尾递归算法时，我们首先应该了解return of the recursive call和return statement of the calling function.之间的情况，一旦完成了，我们应该尝试向递归函数中添加一个秘密的特性/累加器参数，然后决定返回什么。我遵循了博客文章中给出的例子的概念，但我无法解决在博客末尾给出的练习。我无法决定我的累加器参数应该是什么？我应该如何根据累加器参数做出决定。我不想要一个解决方案，而是一些关于我应该如何思考来解决这个问题的建议。下面是练习代码：
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 提前感谢！
回答 1
Stack Overflow用户
发布于 2017-11-08 07:12:02
我发布这篇文章是为了替换我昨天的评论，并展示代码。
在递归算法中，每个调用都创建一个堆栈框架，其中包含函数的局部变量和传递的参数。所有堆栈帧一起保存某种状态信息。当您要避免递归时，将不会有额外的堆栈帧。因此，必须在非递归函数中维护数据的重要部分。
现在是密码。我试着严格按照指示办事。
这是最初的来源。我只是省略了docstring，并将elif替换为return之后立即出现的ifs (只是首选的样式问题)。
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传递给它。该函数将获得一个新参数，其含义是“如果找不到更好的东西，请返回此参数”。在更改之前，它是“如果找不到任何东西就不返回”。所以我们只需要替换零值。我称新参数为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.valhttps://stackoverflow.com/questions/47161712
复制相似问题
腾讯云开发者
