Explain: Recursion in Python


#1
def depth(tree):
  if not tree: return 0
  left_depth = depth(tree["left_child"])
  right_depth = depth(tree["right_child"])
  if left_depth > right_depth:
    return left_depth + 1
  else:
    return right_depth + 1
tree = {
  'left_child': {
    'left_child': {
      'left_child': None, 
      'data': 1, 
      'right_child': None
    }, 
    'data': 2, 
    'right_child': None
  }, 
  'data': 3,
  'right_child': {
    'left_child': None,
    'data': 4, 
    'right_child': None
  }
}

print(depth(tree)) #??? 2???

Sorry, I can not understand how it works??? I can not describe the callback, execution context in this case??? Does anyone can help??? Thanks for in advance.

iteration-recursion-python-depth


#2

That is the depth of the left_child, and therefore the depth of the tree, as it is the greatest depth.

What is difficult to see is that each recursion is handing in a smaller object. Once the increment reaches an empty object, or a non-existing one, it passes the not tree test and recursion stops. We don’t see the 0 unless the tree is empty to start. What we see when the call stack winds down, in this case, 2, is after all the returns.

During recursion, the returns are abeyed, and reside temporarily in a call stack. When the base case has been reached, (return 0), that is the signal to begin popping off the returns in the call stack, which in turn accumulate until the last return is handled. It is that return that the initial caller sees.

Even less obvious in all of this is that returns depend upon the previous return value, so there is no way to resolve any of them if the stack doesn’t wind down.


This is what happens when the call stack runs out of space:

HACF

Halt, And Catch Fire.

A runaway recursion will eat up the call stack space in no time. When that happens, check your base case, first, then look for errors.

crashing is a good way of halting, and burning is a good way of catching fire.

“Crash and burn”.

Not the friendliest of euphemisms, but apropos.


#3

Thank mft.

I’ve got some ideas from your sharing. But it’s still really tricky for me.
I’ve also found a nice tool to visualize the recursion.


#4

It’s enough to understand that the problem can be solved if the subproblems can be solved, and that the subproblems are always smaller and eventually hit the trivial case.

The key is that the problem is made smaller each time, and that there is a trivial case.

Your whole algorithm is:

leaf:   the depth is 1
others: deepest child + 1

A child is a smaller problem than the current tree, and the trivial case of a leaf is always reached.

If you agree that it is correct and always terminates, then that’s all you need to understand.