algorithm - 如果不只是在伪代码中调用函数，而是编写一个返回函数（尤其是关于 CLR），那是否有意义？

Question

如果不只是在伪代码中调用函数，而是编写一个返回函数（尤其是关于 CLR），那是否有意义？

例如是

if x == NIL or x.key == k
   return x
if x.key <= k
   return Tree-Search(x.left,k)
else 
   return Tree-Search(x.right,k)

等于

if x == NIL or x.key == k
   return x
if x.key <= k
   Tree-Search(x.left,k)
Tree-Search(x.right,k)

标签： algorithmtreepseudocode

Answer 1

return肯定是需要的。大概引用的代码是Tree-search函数的主体，所以它实际上看起来像这样：

function Tree-Search(x, k)
    if x == NIL or x.key == k
       return x
    if x.key <= k
       return Tree-Search(x.left, k)
    else 
       return Tree-Search(x.right, k)

现在这个函数应该从树中返回一个节点——键等于k​​的节点。如果您不使用return，则该函数将不会返回任何内容（第一个if条件为真的情况除外）。

其次，这个函数调用自己：这是有意的。它是一种递归算法。这个想法是，如果当前节点不匹配，则搜索以其子节点为根的每个子树。为此，您可以使用相同的功能。当当前节点没有子节点或匹配时，此递归停止。

return不带和带的代码都return进行递归调用。不同之处在于，没有的版本不会return对从该调用返回的内容做任何事情：它完全忽略它。一个 withreturn将捕获返回的值并将相同的值返回给它自己的调用者。

想象一下执行进行了几个嵌套的递归调用，那么您可以将此状态想象为一个递归树，其中每个递归调用都处于挂起状态；等待更深的呼唤返回。让我们假设最后一个有x.key == k. 在这种情况下，x返回该特定信息。但它不会返回给初始调用者，而是返回给正在等待结果的递归调用者。如果返回的值没有再次返回给递归树中上一级的调用者，那么调用者将不会知道这个匹配x。所以每个调用者都必须取回它x并将它也返回到递归树的上方。最后，最初的调用者也会得到x。