Recursion & Data Structures Lab

Pick a recursive algorithm, provide an input, and watch the call tree unfold. See every stack frame, trace return values back up the tree, compare call counts across algorithms, and study the Java implementations.

Guided Experiment: Linear vs Exponential Recursion

Hypothesis

Setup

Run Experiment

Analyze

Conclude

How will the number of recursive calls differ between factorial(n) and fibonacci(n) as n increases? Predict the call counts for n = 4, 5, 6.

Write your hypothesis in the Lab Report panel, then click Next.

Call Tree(5 calls)

Depth 0Depth 1Depth 2Depth 3Depth 4Base case

Controls

Algorithm

Computes n! = n × (n−1) × ... × 1 recursively. Each call multiplies n by factorial(n−1) until reaching the base case n ≤ 1.

n (integer 0−20)

Presets

Analysis

Result

120

Total Calls

Max Depth

Time Complexity

O(n)

Space Complexity

O(n)

Base Cases

Java Implementation

public static long factorial(int n) {
    if (n <= 1) {
        return 1;  // base case
    }
    return n * factorial(n - 1);  // recursive case
}

Data Table

(0 rows)

#	Algorithm	Input	Result	Total Calls	Max Depth	Time	Space

Hypothesis

0 / 500

Observations

0 / 500

Conclusions

0 / 500

Reference Guide

How Recursion Works

A recursive function calls itself with a smaller or simpler version of the original problem. Each call creates a new stack frame that holds its own copy of parameters and local variables.

// Recursive factorial
public static int factorial(int n) {
    if (n <= 1) return 1;       // base case
    return n * factorial(n - 1); // recursive case
}
// factorial(4) = 4 * factorial(3)
//              = 4 * 3 * factorial(2)
//              = 4 * 3 * 2 * factorial(1)
//              = 4 * 3 * 2 * 1 = 24

Every recursive function needs at least one base case that stops the recursion and at least one recursive case that moves toward the base case.

Base Case & Recursive Case

The base case is the simplest version of the problem that can be solved directly without further recursion. Without it, the function would recurse forever and cause a stack overflow.

// Binary search: two base cases
public static int search(int[] arr, int t, int lo, int hi) {
    if (lo > hi) return -1;      // base: not found
    int mid = (lo + hi) / 2;
    if (arr[mid] == t) return mid; // base: found
    if (arr[mid] < t)
        return search(arr, t, mid + 1, hi); // right half
    return search(arr, t, lo, mid - 1);     // left half
}

Each recursive call must make progress toward the base case. For factorial, n decreases by 1. For binary search, the search range halves. If the problem does not shrink, recursion is infinite.

Call Stack & Memory

Each recursive call pushes a new frame onto the call stack. The stack grows until a base case is reached, then frames pop off as return values flow back up to the caller.

// Call stack for factorial(4):
// [factorial(4)]              -- push
// [factorial(4), factorial(3)] -- push
// [factorial(4), factorial(3), factorial(2)] -- push
// [factorial(4), factorial(3), factorial(2), factorial(1)] -- base
// [factorial(4), factorial(3), factorial(2)] -- return 1
// [factorial(4), factorial(3)]  -- return 2
// [factorial(4)]               -- return 6
// []                           -- return 24

The maximum stack depth equals the maximum recursion depth. Deep recursion (thousands of calls) can cause StackOverflowError in Java, which defaults to a stack size of about 512 KB.

Recursion vs Iteration

Every recursive algorithm can be rewritten iteratively using an explicit stack or loop. Iteration avoids the overhead of stack frames and the risk of stack overflow.

// Iterative factorial (no stack overhead)
public static long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
// Uses O(1) space vs O(n) for recursive version

Choose recursion when the problem has a natural recursive structure (trees, divide-and-conquer, backtracking). Choose iteration when stack depth could be large or when tail recursion is not optimized by the runtime.