What is a recursion tree?
A recursion tree is a visual representation of every call a recursive function makes. Each node shows the arguments passed in and the value returned. Parent-child edges represent which call spawned which sub-call. By reading the tree top-down you can trace the exact execution order and understand how the problem decomposes into smaller sub-problems.
Why memoization matters
Many recursive algorithms revisit the same sub-problems multiple times; Fibonacci is the classic example where fib(3) is computed more than once. Memoization stores results of previously solved sub-problems so they are returned instantly on repeat calls. This technique transforms exponential time complexity into polynomial or linear time, which is the core idea behind dynamic programming.
Reading the call stack
The call stack is the chain of active function calls at any moment during execution. In this visualizer, the depth of a node corresponds to its position on the stack. Deep trees mean more stack frames, which can lead to stack overflow errors in real programs. Observing stack depth helps you understand memory usage and identify when an iterative approach might be safer.
Common recursion patterns
Linear recursion calls itself once per invocation; examples include factorial and linked list traversal. Binary recursion makes two calls per invocation; Fibonacci and merge sort follow this pattern. Tree recursion generalizes to three or more branches, as seen in Tower of Hanoi. Understanding these patterns helps you predict time complexity before writing any code.