Recursion -2

Introduction

In Part 1, we understood what recursion is, how the Principle of Mathematical Induction (PMI) maps to the three steps of a recursive solution, and solved the factorial problem. In this part, we will solve two more classic problems - the Nth Fibonacci number and the power of a number - and learn how to analyse the time and space complexity of a recursive solution.

Quick recap of the three steps:

• Base case: the condition at which the function stops calling itself.
• Recursive call: the function invokes itself on a smaller version of the problem.
• Small calculation: the work done in each call, before or after the recursive call.

Problem 1 - Nth Fibonacci Number

The Fibonacci sequence is defined as: 0, 1, 1, 2, 3, 5, 8, 13, ...
Each number is the sum of the previous two numbers.

F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.

Approach using the three steps:

1. Base case: This time we need two of them - F(0) = 0 and F(1) = 1 - because every value depends on the previous two.
2. Recursive call: F(n-1) and F(n-2) are the smaller versions of the problem. (Induction hypothesis: assume both are already solved.)
3. Small calculation: Add the two results - F(n) = F(n-1) + F(n-2).

Input assumption: n must be a non-negative integer (n >= 0). A negative input is unsupported: it misses both base cases and keeps recursing until the stack runs out, crashing with a StackOverflowError. In production code, validate the input and throw an IllegalArgumentException for negative values.

Pseudocode:

function fib(n):
    if n == 0:          // base case 1
        return 0
    if n == 1:          // base case 2
        return 1
    return fib(n-1) + fib(n-2)   // recursive calls + small calculation

Java code:

public static int fib(int n){
    if (n == 0) // base case 1
        return 0;
    if (n == 1) // base case 2
        return 1;
    return fib(n-1) + fib(n-2); // recursive case
}

Dry run for n = 4 (recursion tree):

              fib(4)
             /      \
        fib(3)      fib(2)
        /    \      /    \
    fib(2) fib(1) fib(1) fib(0)
    /   \
fib(1) fib(0)

Computing from the bottom up: the leaf values fib(1) = 1 and fib(0) = 0 give fib(2) = 1, then fib(3) = fib(2) + fib(1) = 2, and finally fib(4) = fib(3) + fib(2) = 3.

Note: Look at the tree carefully - fib(2) is calculated twice. As n grows, the same subproblems are recalculated again and again. Each level of the tree has up to twice as many calls as the level above, so the total call count grows exponentially - bounded by about 2^n - which is why this approach takes O(2^n) time. In a quick test with OpenJDK 11, fib(42) already took about a second, so this naive version is only practical for small n. This repeated work is called overlapping subproblems, and removing it leads us to an optimization technique called memoization, which we will cover in the next part.

One more limit: integer overflow can silently produce incorrect results. An int in Java can hold values only up to about 2.1 billion, and fib(47) already crosses that limit and overflows into a wrong (even negative) value. For larger inputs, use long - still finite, just bigger - or BigInteger.

Problem 2 - Power of a Number

Problem statement: Given a base x and an exponent n, find x^n.

Approach using the three steps:

1. Base case: We know that x^0 = 1, so n = 0 is our base case.
2. Recursive call: P(x, n-1) is the smaller version of the problem. (Induction hypothesis: assume we already know x^(n-1).)
3. Small calculation: Multiply once - P(x, n) = x * P(x, n-1).

Input assumption: n must be a non-negative integer (n >= 0). A negative exponent is unsupported: it misses the base case and recurses until the stack runs out (StackOverflowError).

Pseudocode:

function power(x, n):
    if n == 0:               // base case
        return 1
    return x * power(x, n-1) // recursive call + small calculation

Java code:

public static int power(int x, int n){
    if (n == 0) // base case
        return 1;
    return x * power(x, n-1); // recursive case
}

Dry run for power(2, 4):

power(2, 4) = 2 * power(2, 3)
            = 2 * (2 * power(2, 2))
            = 2 * (2 * (2 * power(2, 1)))
            = 2 * (2 * (2 * (2 * power(2, 0))))
            = 2 * (2 * (2 * (2 * 1)))
            = 16

Overflow watch: power can also overflow int: 2^31 already crosses the int limit. long pushes the boundary further but is still finite, so very large results need BigInteger.

Time and Space Complexity of a Recursive Solution

For every recursive solution, ask two separate questions:

• How many calls happen in total? This decides the time. The power function makes about n calls, so it takes O(n) time. The naive Fibonacci function makes up to about 2^n calls in total (exponential growth), so it takes O(2^n) time.
• How many calls are alive on the stack at the same time? This decides the extra memory. It is the maximum depth of the recursion tree, not the total number of calls. The power function goes n levels deep, so it uses O(n) stack space. The Fibonacci tree has up to about 2^n total calls, but its depth is only n - the longest chain is fib(n) -> fib(n-1) -> ... -> fib(2) -> fib(1) - so it also uses O(n) stack space.

This stack depth is the hidden cost of recursion: an iterative loop for the same problems would use only O(1) extra space. And if the input is large enough (say, power(x, 100000)), the depth itself can crash the program with a StackOverflowError, even when the total work would have been manageable.

Summary

• A problem can have more than one base case (Fibonacci needs two).
• Always define the valid input range - a negative input with no matching base case means a stack overflow, not a wrong answer.
• Drawing the recursion tree is the easiest way to dry run, to count total calls (time), and to find the maximum depth (stack space).
• Watch the data-type limits: int overflows at fib(47), 13!, and power(2, 31); long is bigger but still finite.

In the next part, we will see how memoization removes the repeated calculations in Fibonacci and takes the first step from recursion towards dynamic programming. Stay tuned!

---

This article was drafted with the help of AI and reviewed by me before publishing.