Counting the leaves of a binary tree using recursion: the final return statement of (recursive funct-CodePudding

I have been learning binary trees lately and have looked through the code for counting the leaves.

This is the recursive function to count the leaves:

def __count_leaves_recursive(self, node):

    if node == None:
        return 0

    elif node.left == None and node.right == None:
        return 1

    else:
        return self.__count_leaves_recursive(node.left)   self.__count_leaves_recursive(node.right)

When learning how recursion works with trees, the Python Tutor visualisation tool has been invaluable. However it hasn't helped me visualise the final return statement. I am struggling to visualise what's happening when a recursion function is added to another recursive function in the same line.

Is it simply the same as any other time the program reaches a recursive function? In that, the program simply records where it enter the function in order to return to the same spot when the function has been completed?

CodePudding user response：

Is it simply the same as any other time the program reaches a recursive function?

Yes, you can image that line of code like this:

a = self.__count_leaves_recursive(node.left)
b = self.__count_leaves_recursive(node.right)
return a   b

So the first recursive call has to finish completely before the second one is launched. When that second recursive call also has finished its job, both returned values are summed up, and that value is returned to the caller.