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.
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!