Recursion is a function that solves a problem by calling itself on smaller pieces.
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.
n = 5, then 7. How fast does the number of calls grow?n. Which nodes turn purple, and why do they have no children?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.