Fibonacci Using Recursion in DSA Java - Time & Space Complexity

Time Complexity: Fibonacci Using Recursion

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to find a Fibonacci number grows as the input number gets bigger.

Specifically, how many steps does the recursive method take as the input increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This code calculates the nth Fibonacci number by calling itself twice for smaller values until it reaches the base cases.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two recursive calls per function call.
• How many times: Each call splits into two more calls until reaching base cases, causing many repeated calculations.

How Execution Grows With Input

Each call creates two more calls, so the total calls grow very fast as n increases.

Input Size (n)	Approx. Operations
10	About 177 calls
20	About 21,891 calls
30	About 2,692,537 calls

Pattern observation: The number of calls roughly doubles with each increase in n, leading to exponential growth.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed grows very fast, doubling with each step up in n, making it inefficient for large inputs.

Common Mistake

[X] Wrong: "The recursive Fibonacci runs in linear time because it just counts down from n to 0."

[OK] Correct: Each call makes two more calls, so the total calls grow exponentially, not linearly.

Interview Connect

Understanding this helps you explain why naive recursion can be slow and why techniques like memoization improve performance.

Self-Check

"What if we add memoization to store results of previous calls? How would the time complexity change?"

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the difference of the two preceding numbers

B. Each number is the sum of the two preceding numbers

C. Each number is the product of the two preceding numbers

D. Each number is the square of the previous number

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence is defined such that each number is the sum of the two numbers before it.

2. Step 2: Relate to recursion

   Recursion calls the function for the two previous numbers and adds their results to get the current number.

3. Final Answer:

   Each number is the sum of the two preceding numbers -> Option B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds two previous numbers to get next [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing difference with sum
• Assuming Fibonacci squares previous number

2. Which of the following is the correct base case syntax for a recursive Fibonacci function in Java?

easy

A. if (n == 0 || n == 1) return n;

B. if (n == 0 && n == 1) return n;

C. if (n = 0 || n = 1) return n;

D. if (n != 0 || n != 1) return n;

Solution

1. Step 1: Identify correct base case condition

   The base case must check if n is 0 or 1 using '==' for comparison and logical OR '||'.

2. Step 2: Check syntax correctness

   if (n == 0 || n == 1) return n; uses correct comparison operators and logical OR. Others use incorrect operators or logic.

3. Final Answer:

   if (n == 0 || n == 1) return n; -> Option A

4. Quick Check:

   Base case uses '==' and '||' [OK]

Hint: Use '==' for comparison and '||' for OR in base case [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Using '&&' instead of '||' in base case
• Incorrect negation or logic in condition

3. What is the output of the following Java code?

public class FibTest {
  public static int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 7

B. 5

C. 4

D. 3

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + 1 = (1 + 0) + 1 = 2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The main method prints fib(4), which is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Calculate fib(n) by adding fib(n-1) and fib(n-2) [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Miscomputing base cases
• Adding wrong recursive results

4. Identify the error in this recursive Fibonacci function and select the fix:

public static int fib(int n) {
  if (n == 0 || n == 1) {
    return 0;
  }
  return fib(n - 1) + fib(n - 2);
}

medium

A. Change 'return 0;' to 'return n;' in base case

B. Change 'if' condition to 'n == 2 || n == 3'

C. Add a loop inside the function

D. Remove the base case entirely

Solution

1. Step 1: Analyze base case return value

   The base case returns 0 for both n=0 and n=1, but fib(1) should return 1.

2. Step 2: Correct base case return

   Return n for base cases 0 and 1 to correctly represent Fibonacci values.

3. Final Answer:

   Change 'return 0;' to 'return n;' in base case -> Option A

4. Quick Check:

   Base case returns n for n=0 or 1 [OK]

Hint: Base case must return n, not always 0 [OK]

Common Mistakes:

• Returning 0 for fib(1)
• Changing base case condition incorrectly
• Removing base case causing infinite recursion

5. You want to find the 6th Fibonacci number using recursion but want to avoid repeated calculations. Which technique can you apply to optimize the recursive Fibonacci function?

hard

A. Increase the base case to n == 5

B. Replace recursion with an infinite loop

C. Use memoization to store and reuse computed results

D. Use a global variable to count calls

Solution

1. Step 1: Understand recursion inefficiency

   Recursive Fibonacci recalculates the same values many times, causing slow performance.

2. Step 2: Apply memoization

   Memoization stores results of fib(n) in a cache so repeated calls return cached values, improving speed.

3. Final Answer:

   Use memoization to store and reuse computed results -> Option C

4. Quick Check:

   Memoization avoids repeated calculations [OK]

Hint: Cache results to avoid repeated recursive calls [OK]

Common Mistakes:

• Changing base case incorrectly
• Using infinite loops causing crashes
• Counting calls without optimization