Recursion

The problem

Some problems contain smaller copies of themselves.

• Sum of 1..n is n plus the sum of 1..n-1.
• The depth of a tree is 1 plus the larger depth of its two subtrees.
• x^n is x^(n/2) squared, times x if n is odd.

Recursion means a function that calls itself on a smaller input. It is the natural way to write these, and the base of backtracking, dynamic programming and tree algorithms later in the track.