Trying to teach my brain to spot head vs tail recursion. Is this tail recursion ? The recursive statement is at the end , but there is some data being stored in the total variable too, so that got me confused.

def visible_tree_node(root:Node) -> int:
    def dfs(root:Node,current_max:int) -> int:
        if not root:
            return 0
        total = 0
        if root.val >= current_max:
            current_max = root.val
            total  =1
        total  = dfs(root.left,current_max)
        total  = dfs(root.right,current_max)

        return total

    return dfs(root,-float('inf'))

CodePudding user response：

The dfs call in visible_tree_node is in tail position. That call, and only that call, could have its stack frame omitted via

Similarly, a while loop will compile to a block which has a conditional jump at the end. The conditional jump will go backwards to the start of the loop if some condition is true and onward if false.

a
while b:
  c
d

In CFG form, a call is in tail position if it is at the very end of the function. We can recursively define those rules in terms of Python constructs as follows. I'm most familiar with static single-assignment, so I'll use that in the examples below.

• The very last line of a function is in tail position, since there are no instructions after it.
• The expression of a return statement in tail position is itself in tail position, for similar reasons.
• If an if statement is in tail position, then the last line of the if branch, as well as any elif or else branches, are all in tail position. An if (and else and elif) causes the CFG to split, and if it's in tail position then the split won't come back together; it'll simply return to the caller, so as far as CFG analysis is concerned, we're still at the end of the function.
• If a loop (for or while) is in tail position, then any statement immediately succeeded by a break inside this loop is in tail position. This one is complicated, so some optimizers may miss it. A break inside a loop would compile in SSA to a goto the end of the loop, and if the end of the loop is also the end of the function (i.e. tail position), then the thing right before the break is as well.
• If a try ... finally block appears in tail position, then the last line of the finally portion is also in tail position.

Some constructs are never in tail position. For example, the inside of a with is never in tail position, because with has to run code after the block is done. These rules are not comprehensive; they're just what I could come up with right now on the spot based on how the various Python constructs compile to CFG. A comprehensive list would require a more detailed analysis of control flow that wouldn't fit in the scope of this answer.

I've never heard the term "head recursion" before. I suppose it could be defined to mean "the recursion is the very first thing" by rules basically dual to those above, but it doesn't sound like a very useful concept (since it would be impossible to optimize around).