The one-line definition: a function that calls itself until it hits a stopping condition.

That's it. Everything else is just patterns.

An example: Russian dolls (matryoshka)

You open a Russian doll. Inside is a smaller doll. Open it → another smaller doll inside. Keep opening until you find the tiniest doll with nothing inside. Then you know the answer: "there were 5 dolls."

You could write that as a recipe:

openDoll ( doll ): if doll is empty inside : return 1 ← the stopping condition else : return 1 + openDoll ( inside doll ) ← the function calls itself

Enter fullscreen mode

Exit fullscreen mode

Two ingredients every recursion needs:

Base case — when to stop ( if doll is empty ).

Recursive step — call yourself on a smaller version of the problem ( openDoll(inside doll) ).

If you forget the base case, you recurse forever and crash.…