Recursion

Solving a problem with smaller copies of itself.

The shape

A recursive function needs a base case that stops and a step that moves towards it. Trees, graphs and divide and conquer algorithms are naturally recursive.

Every call uses stack space, so depth is bounded.
Any recursion can be rewritten as a loop with an explicit stack.

Memoisation

Storing results of calls you have already made turns exponential recursion into linear work. Naive Fibonacci recomputes the same values billions of times; a cache fixes it in one line.