我在阅读关于将递归算法转换成迭代算法的文章。我看到了一篇博客文章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
谢谢您的提前帮助!