Python recursion and return

Question

I'm new to the concept of recursion, had never practiced this magic in my coding experience. Something I'm really confused about Python recursion is the use of "return". To be more specific, I don't quite understand when to use return in some situations. I've seen cases where the return is used before recursion, and cases return is not needed at all.

For example:

A Leetcode Question: "Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL."

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """

        if root == None:

            return root

        if root.val == val:

            return root

        elif root.val > val:

           return self.searchBST(root.left,val)

        else:

           return self.searchBST(root.right,val)

Why do I need to return "self.searchBST(root.left,val)" and "self.searchBST(root.right,val)"? If there is no return added for the two lines, would't the program still run recursively until the conditions of root.val == val or root== None is met, and a value is returned? (I know it's not the case in practice, I'm just trying to conceptualize it).

Moreover, could someone kindly show me the general guideline for using return in recursions? Thank you in advance!

Answer 1

If you just write:

self.searchBST(root.left,val)

instead of

return self.searchBST(root.left,val)

it will perform the recursive search but won't return the result back to the block in which it is invoked. When it gets to the value you want (or doesn't find it), that call will do

return root

But the previous call will just discard this value, rather than returning it back up the recursion chain.

Answer 2

A return statement exits the currently running function and returns a return value, which can then be used like any other value in Python: assigned to a variable, passed as the argument to another function, or ... returned as the return value of the calling function.

def some_func():
    return 'result'

x = some_func()  # after this, x == 'result'

If you call a function without capturing the return value, it just gets lost. So, if you just call some_func(), it will get executed.

some_func()  # this works, but 'result' is lost

The same goes for a function that calls another function, even if that other function is itself:

def some_other_func1():
    x = some_func()
    return x

def some_other_func2():
    return some_func()  # exact same result as some_other_func1()

def some_recursive_func(n):
    if n == 0:
        print('Reached the end')
        return n
    else:
        print(f'At {n}, going down')
        return some_recursive_func(n-1)

print(some_recursive_func(3))  # prints a bunch of lines, but always prints `0` at the  end

Answer 3

Let's take an even simpler example and you can apply the same logic to your method as well,

def fact(n):
    #Base case
    if n in [0, 1]:
        return 1

    #Recursion. Eg: when n is 2, this would eventually become 2 * 1 and would be returning 2 to the caller
    return n * fact(n-1)

In general a recursive function will have 2 cases, one being the base case and the other being recursive call to self. And remember, this is a function and ideally is supposed to return something to the caller. That is where return statement would be needed. Otherwise you wouldn't be returning right value to the caller.

If there is no return added for the two lines, would't the program still run recursively until the conditions of root.val == val or root== None is met, and a value is returned

Value is returned yes. But it would be returned to previous call (and so on) and hence it would return to one of self.searchBST(root.left,val) or self.searchBST(root.right,val). You would still need to return from this point to the caller of the function. Hence you would need to have return self.searchBST(root.left,val) or return self.searchBST(root.right,val).