4

I was brushing up on the concept of recursion and working with binary trees. I don‘t understand the difference between instances of using a return statement with a recursive call and other times when return is not used. I‘ll give code illustrating my question.

Here is a function that checks if a value is present in a BST:

public boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }

    if (value == current.data) {
        return true;
    }

    //HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
    return value < current.data
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
   }
}

Here is a function for insertion of data into a BST:

public Node insert(Node current, int data) {
    if (current == null) {
        return createNode(data);
    } else if (data < current.data) {
        //RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
        current.left = insert(current.left, data);
    } else if (data > current.data) {
        current.right = insert(current.right, data);
    }

    return current;
}

I think my question boils down to: “When should we return a recursive call and when should we not?”

james
  • 131
  • 9
  • 1
    “*The recursive call is preceded by a return statement*” - not really, the statement including the recursive call is still evaluated to obtain the return value – MTCoster Feb 02 '19 at 23:05
  • 1
    Just like `return 1 + 2` requires computing the result of the addition before returning, `return somefunction()` requires computing the result of the function call, regardless of how deep the recursion goes. You don't necessarily need to return anything, if your recursion does not require something returned - you simply need to terminate the recursion, using your base-case. – Jeppe Feb 02 '19 at 23:15
  • Simple answer is: a "recursive call"[!] is never returned - none of your excamples returns a call.(period) The return value(!) of the method on the other hand is what the methode is supposed to "compute". A method that adds numbers will probably return the sum, So that entirely depends on what you decide the method should do - there is no general rule. – kai Feb 02 '19 at 23:21
  • Well there are two rules when it comes to recursion: a) try to avoid it. b) if you cant avoid it, try to make it endrecursive(return is the last statement). [Sidenode if b) is possible the compiler will try to remove the recursion ... ] – kai Feb 02 '19 at 23:29
  • @kai Try to avoid it why? Some algorithms, such as this one, are naturally recursive, and best expressed that way – user207421 Feb 03 '19 at 20:12
  • first, recursive code is for most people difficult to follow. So while you and a few other exceptions might have no diffculties all others that try to understand the code have a hard time. The hard time recursion gives the op shows what i mean. Second a machine doesn't know nothing about recursion. It has to emulate it via stacks or replace it with nonrecursive code. If it has to emulate it, it kills performance. You're kinda work against the machine which may or may not be able to compensate the penalty. Sure there are exceptions where recursion makes code better but they are rare. – kai Feb 03 '19 at 20:23

3 Answers3

0

There are two types of functions presented, so there are two separate rules we need to follow.

Take the first function you provided:

public boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }

    if (value == current.data) {
        return true;
    }

    //HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
    return value < current.data
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
   }
}

This function is intended to find a single target value and return it. In this case, we return a recursive call when we want to return a value that we know will be provided by a single child of the node being tested.

However, take the insertion example:

public Node insert(Node current, int data) {
    if (current == null) {
        return createNode(data);
    } else if (data < current.data) {
        //RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
        current.left = insert(current.left, data);
    } else if (data > current.data) {
        current.right = insert(current.right, data);
    }

    return current;
}

This code is intended to accomplish a different type of task. Rather than seeking a single target value, this recursive function is intended to modify the existing tree. In this case, we return only the modifications that we want to make to the existing tree (or the duplicate value).

Fluffy the Togekiss
  • 345
  • 2
  • 11
  • 1
    I'm not sure I follow your second code-snippet. If you pass the root-node to this function, and return current.left - then you essentially throw away the right part of the tree, right? – Jeppe Feb 02 '19 at 23:25
  • ...I had a massive brain shutdown. Let me fix the wrongdoings of my past self. – Fluffy the Togekiss Feb 03 '19 at 01:21
  • My code has now been fixed. I now return the inserted Node without overwriting any existing Nodes. Thanks for pointing that out to me, Jeppe! – Fluffy the Togekiss Feb 03 '19 at 01:25
  • Have you tried running it? Your code is still wrong, the code posted by OP is correct. You shouldn't return null for duplicates, you should return current without modifying it - and returning the result of the recursion, throws away half the tree for each node. – Jeppe Feb 03 '19 at 10:02
  • I’m returning the inserted node, not the entire tree. There’s no need to return the tree; to call this non-static function, you necessarily have access to the root node to begin with. I approached it this way because the given code includes return createNode(), which implies that the OP wants to return the node they are adding to the tree. But perhaps I am misunderstanding the OP’s question? – Fluffy the Togekiss Feb 03 '19 at 18:47
  • 1
    `return current;` shows you that the inserted node is not to be returned, but in effect, the 'new' tree. OP has provided two examples of recursions - they're not wrong AFAIK. Your code however, passes a value down the tree, creates a new node at the bottom and returns it back up. But it never attaches it to the tree, which was the point of `current.left = insert(current.left, data);`. Try drawing a small example, using the original code. – Jeppe Feb 03 '19 at 19:02
  • My understanding was that the given function called createNode() was implied to attach directly to the tree, so I did not do so explicitly in my code. That’s why I understood the second example to be incorrect and changed that return statement; my understanding of what the code was intended to do and the final return statement was doing were contradictory. Looking at it, I think I’m understanding the intention a bit better. Let me edit once more. – Fluffy the Togekiss Feb 03 '19 at 19:41
  • Alright, I finished that edit. Are we on the same page now? – Fluffy the Togekiss Feb 03 '19 at 20:09
0

Since Java doesn't do tail-recursion optimization, you never have to "return a recursive call". See "Why doesn't Java have optimization for tail-recursion at all?"

See "What is tail recursion?" if you want to learn about how that works in functional languages, but it isn't applicable to Java.

In Java, you do the recursive call wherever in the method it'll make more sense to you. You don't have to do it as part of a return statement.

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • if we have the same understanding of the term: java does try to replace recursion wherever possible. It can't do it however, if the structure is too complex. "Tail recursion" has a simple structure and assist the compiler in optimizing the code. – kai Feb 03 '19 at 00:01
  • @kai Java does **not** do tail-recursion optimization. Just tested in Java 11 with the `tailrecsum` function shown in the [link](https://stackoverflow.com/a/37010/5221149) above, and I get `StackOverflowError`. – Andreas Feb 03 '19 at 00:08
  • For now I can only can give you a link to IBM. For Oracle i need to dig. https://www.ibm.com/support/knowledgecenter/en/SSYKE2_8.0.0/com.ibm.java.vm.80.doc/docs/jit_optimize.html Shure you are right: if you call a "unknown function" it gets too complex. – kai Feb 03 '19 at 00:14
0

The return keyword preceding the recursion is not different from this:

boolean res = value < current.data
    ? containsNodeRecursive(current.left, value)
    : containsNodeRecursive(current.right, value);

return res;

Either way the recursion is fully evaluated before the current function-call can return.

“When should we return a recursive call and when should we not?” - you're not returning a recursive-call, you're returning the result of the recursion, e.g a boolean. You can return the result of a function-call immediately if you do not have any more processing to do. This obviously requires the function-call to return the same type as the current function is expected to return, which is guaranteed for recursions as it calls "itself".

For your first code-snippet, consider what the function does. It searches for a value, and if found further down the tree, then that boolean value is simply forwarded back up the tree.

In your second example, the tree is being changed as part of the recursion. For any node current, the recursion returns the left/right subtree, which must then overwrite the existing left/right subtree before being able to return.

Jeppe
  • 1,830
  • 3
  • 24
  • 33