Recursion Call Tree

Recursion is a function that solves a problem by calling itself on smaller pieces.

The idea

Russian nesting dolls: to know what is inside the biggest doll you open it, find a smaller doll, and ask the same question. At the tiniest doll (the base case) the answer is known and you start returning answers back up.

fib(n) = fib(n-1) + fib(n-2) with fib(0) = 0 and fib(1) = 1. Each call is a node in a call tree. You will see the same sub-problem (like fib(3)) calculated again and again. Memoization means writing each answer in a notebook the first time, so a repeated call just reads it back instead of branching further.

Watch it work

Try it

Common mistakes

How fast is it?

Plain fib: about O(2n) time, because the call tree roughly doubles each level. Memoized: O(n) time, since each value is computed once, and O(n) space for the memo map and call stack.