Count the Calls Made by Naive Fibonacci

Easy15 min

Topics

BasicsComplexityRecursion

Companies

TCSInfosysWipro

The naive recursive Fibonacci function calls itself twice for every value of 2 or more. Given n, return how many calls in total fib(n) makes, counting the first call. This is the standard example of exponential time: every call branches into two, and the same subproblems are solved again and again. Exponential algorithms become unusable very quickly — fib(50) would need tens of billions of calls — which is why spotting and removing repeated work matters so much.

Test Case 1:

Input:n = 4

Output:9

Explanation:fib(4) calls fib(3) and fib(2), and so on down the tree — 9 calls in total, with fib(2) computed twice.

Test Case 2:

Input:n = 1

Output:1

Explanation:fib(1) is a base case, so only the first call happens.

Constraints

◆0 ≤ n ≤ 25

Try the Dry Run

Mode

Approach

Approach & Solutions

Recurse and Count Every CallBrute

Run the textbook recursive Fibonacci — fib(k) = fib(k − 1) + fib(k − 2), with fib(0) = 0 and fib(1) = 1 — and add one to a counter at the start of every call. Each call splits into two more, so the number of calls roughly doubles every time n grows by one.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    int calls = 0;

    int fib(int k) {
        calls++;
        if (k < 2) {
            return k;
        }
        return fib(k - 1) + fib(k - 2);
    }

    public int fibCalls(int n) {
        calls = 0;
        fib(n);
        return calls;
    }
}

Build the Counts Bottom-UpOptimal

The calls made by fib(k) follow their own rule: one for the call itself plus all the calls of fib(k − 1) and fib(k − 2). So calls(k) = 1 + calls(k − 1) + calls(k − 2), with calls(0) = calls(1) = 1. Build that up from the bottom with two variables, as with Fibonacci itself — n steps instead of exponentially many.

TimeO(n)

SpaceO(1)