When writing a recursive function, when to pass 'count' as argument from one recursive cal-CodePudding

I have written/seen a number of recursive functions. My question is that in many questions, we are often asked to keep a 'count' of something, e.g. "Count the number of leaf nodes in a binary tree".

One recursive function would be:

def countLeavesInTree(root, count= 0): 
    if root.left: 
        countLeavesInTree(root.left, count)
    if root.right: 
        countLeavesInTree(root.right, count)
    if not root.left and not root.right: 
        count  = 1
        return        #How can we increment count by 1 here?- is this right?

    return count

Equivalently to the above, I have seen recursions incrementing 'count' as follows:

def countLeavesInTree(root): 
    count = 0 

    if root.left: 
        count  = countLeavesInTree(root.left)
        return
    if root.right: 
        count  = countLeavesInTree(root.right)
        return
    if not root.left and not root.right: 
        return 1    
    
    return count

When do we use the first approach and when do we use the second? Or does it not matter and both can be used in any cases?

Amended code:

def countLeavesInTree(root):
    count = 0

    if not root.left and not root.right:
        return 1

    else:
        count  = countLeavesInTree(root.left)   countLeavesInTree(root.right)

    return count

CodePudding user response：

Your "amended code" is very close, the only thing you need to add is the guard back to make sure you are not passing a None as a new root.

You want:

def countLeavesInTree(root):
    if not root.left and not root.right:
        return 1

    count = 0

    if root.left:
        count  = countLeavesInTree(root.left)

    if root.right:
        count  = countLeavesInTree(root.right)

    return count

or via a comprehension you might:

def countLeavesInTree(root):
    if not root.left and not root.right:
        return 1

    return sum(
        countLeavesInTree(child)
        for child
        in [root.left, root.right]
        if child
    )

a full simple example might be:

class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.value = val

root = Node("root")
root.left = Node("root.left")
root.left.left = Node("root.left.left") # a leaf
root.right = Node("root.right")
root.right.right = Node("root.right.right") # a leaf
root.right.left = Node("root.right.left") # a leaf

def countLeavesInTree(root):
    if not root.left and not root.right:
        return 1
    return sum(countLeavesInTree(child) for child in [root.left, root.right] if child)

print(countLeavesInTree(root))

With luck, that should give you 3.

You really never want to try to maintain a global like the first version while doing recursion. Python recursion is not great (in that you can unexpectedly reach the default limit rather quickly) so if you wanted to try to maintain a variable like that, it might be better to try to shift out of recursion to a more traditional looping structure.

Perhaps something like:

def countLeavesInTree2(root):
    if not root:
        return 0

    count = 0
    brush_pile = [root]
    while brush_pile:
        current = brush_pile.pop(0)
        if not current.left and not current.right:
            count  = 1
        else:
            brush_pile.extend(
                child
                for child
                in [current.left, current.right]
                if child
            )
    return count