Recursion

Recursion Tree

Visual representation of nested function calls and call-stack execution flow using the Fibonacci sequence.

What is Recursion Tree?

Recursion is a programming technique where a function calls itself to solve smaller subproblems of the same problem. A Recursion Tree visualizes this process by showing each function invocation as a node, and its self-calls as branches. This makes call stack depth, parameter changes, and overlapping computations (like in naive Fibonacci) visible.

Key Characteristics:

  • Every recursive function must contain a base case to terminate execution.
  • Each call allocates a stack frame to store parameters and local variables.
  • Overlapping subproblems lead to exponential growth in naive recursion.
  • Helps visualize depth-first stack execution.

Complexity Analysis

Avg Time Complexity: O(2^N) for naive Fibonacci recursion
Space Complexity: O(N) call-stack depth memory
Best Case: O(1) (input triggers base case directly)
Worst Case: O(2^N) (exhaustive branching tree)

How it Works Step-by-Step

  1. Define Base Case: Check if input N is 0 or 1. If so, return N directly.
  2. Recursive Branching: Otherwise, invoke fib(N - 1) to calculate the left branch.
  3. Compute Right Branch: Invoke fib(N - 2) to calculate the right branch.
  4. Accumulate & Return: Add the results of the two branches: return fib(N - 1) + fib(N - 2).

Code Implementation

Worked Trace Example

Calculating fib(3):
1. fib(3) is not a base case; calls fib(2) and fib(1).
2. fib(2) calls fib(1) and fib(0).
3. fib(1) returns 1 (base case). fib(0) returns 0 (base case).
4. fib(2) returns 1 + 0 = 1.
5. fib(1) (from original fib(3) call) returns 1 (base case).
6. fib(3) returns fib(2) + fib(1) = 1 + 1 = 2.

Ready to Understand Recursion Tree Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Recursion Tree Visualizer →