Recursion

A recursive function calls itself. Each call must be smaller than the one that made it, and there must be a base case that stops. Without the base case the call stack grows until it overflows.

The shape fits data that is already defined the same way. A nested list is either a number or a list of nested lists. A tree is either empty or a node with smaller trees under it. The function says what to do for the small case, then combines the answers from the smaller pieces.

You could write the same walk with an explicit stack. Recursion is that stack, hidden inside the calls. If you can say the base case in a sentence before you write the function, the rest usually follows. If you cannot say it, you are not ready to recurse yet.