Is there a meaning if instead of just calling the function in pseudocode one writes a return function (especially regarding CLR)?

Question

Is there a meaning if instead of just calling the function in pseudocode one writes a return function (especially regarding CLR)?

e.g. is

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)

equal to

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

Answer 1

The return is certainly needed. Presumably the quoted code is the body of the Tree-search function, so it would actually look something like this:

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)

Now this function is supposed to return a node from the tree -- the node whose key is equal to k. If you don't use return then the function will not return anything (except in the case where the first if condition is true).

Secondly, this function calls itself: this is intended. It is a recursive algorithm. The idea is that if the current node does not match, then search each of the subtrees that are rooted in its children. And for that you can use the same function. This recursion stops when the current node has no children or is a match.

Both the code without return and with return make the recursive call. The difference is that the version without return doesn't do anything with what it gets back from that call: it completely ignores it. The one with return will capture the returned value and return the same value to its own caller.

Imagine the execution made several nested recursive calls, then you can imagine this state as a recursion tree where each of those recursive calls is pending; waiting for the deeper call to return. Let's assume the last one has x.key == k. In that case that particular x is returned. But it is not returned to the initial caller, but to the recursive caller which was waiting for the result. If the returned value is not returned again to caller that is up one level in the recursion tree, then that caller will not get to know about this matching x. So each caller must get back that x and return it also upward the recursion tree. Finally the initial caller will get x too.