CODEWITHSUNDEEP
javascriptalgorithmrecursionbinary-search-tree
Tanmay Bhattacharya
Tanmay Bhattacharya

Reputation: 551

return statements in recursive calls

From what I understand about recursive calls, is that when you are recursing into by calling the function ,the statement needs to be a return statement ,because basically when it pops out of the function stack it expects some value from the earlier call .

I have some code like for inserting in a BST 

insertCorrectLocation(root, newNode) {
    if (newNode.data < root.data) {
        if (root.left == null) {
            root.left = newNode
        } else {
            return this.insertCorrectLocation(root.left, newNode)
        }
    }
    else {
        if (root.right == null) {
            root.right = newNode
        } else {
            return this.insertCorrectLocation(root.right, newNode)
        }
    }
}

This works even if I remove the return statements for the calls ,such as 

else {
    if (root.right == null) {
        root.right = newNode
    } else {
        this.insertCorrectLocation(root.right, newNode)
    }
}

How does that happen ?

Upvotes: 3

Views: 1410

Answers (3)

Gerard Setho
Gerard Setho

Reputation: 109

I agree with everything said about not needing an explicit return in recursive function.

But I'm currently looking at a huge recursive function, about 600 lines, with many if-else statements. I think it can be dangerous for long recursive functions to not explicitly return. And while I know there are other problems with a long recursive function, it really doesn't hurt to just return;, especially that is the intention.

Upvotes: -1

Sylwester
Sylwester

Reputation: 48745

There is no requirement to return any values from a function that is mainly for side effects. Recursive functions have no special treatments so it goes for those as well. eg. console.log is mainly for effect and it returns the default value undefined. Thus in your example where a recursive function alters an existing object will be able to use the root node as the whole tree after the process has finished.

The most common error is when the contract is supposed to return a value and you forget to return in some places. Eg. 

function factorial(n) {
  if (n === 1) return 1;

  factorial(n - 1) * n;
}

factorial(1) ; //==> 1
factorial(2) ; //==> undefined

A function that does not explicitly return a value always return undefined. Thus for a factorial returning undefined is clearly a bug, but it did rewind the stack and did all the calculations, only that it didn't use the result.

Upvotes: 4

CertainPerformance
CertainPerformance

Reputation: 370729

In a recursive function, you only need to (explicitly) return if the outer consumer of the recursive function needs to receive a value, for example:

const foundNode = tree.findNode(5);

In this case, since you're only inserting a value, but not retrieving one, there's no need for recursive returns.

(functions will automatically return once they reach the end of their block if there's no return statement, passing control back to the caller)

Upvotes: 8

Related Questions