Fibonacci Using Recursion in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Call

What is the output of the following Java code that prints Fibonacci numbers using recursion?

DSA Java

public class Fibonacci {
    public static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.print(fib(i) + " ");
        }
    }
}

A 1 1 2 3 5 8

B 0 1 1 2 3 5

C 0 1 2 3 5 8

D 1 2 3 5 8 13

💡 Hint

Remember that fib(0) = 0 and fib(1) = 1 in this code.

The recursive function returns n when n is 0 or 1, so fib(0) = 0 and fib(1) = 1. The loop prints fib(0) to fib(5), which are 0, 1, 1, 2, 3, 5.

🧠 Conceptual

intermediate

Number of Recursive Calls for fib(4)

How many total calls to the fib function are made when computing fib(4) using the recursive method below?

DSA Java

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

A 5

B 7

C 9

D 15

💡 Hint

Draw the call tree for fib(4) to count all calls.

fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1), fib(2) calls fib(1) and fib(0), and so on. Counting all calls results in 9 total calls.

🔧 Debug

advanced

Identify the Error in Fibonacci Code

What error will occur when running this Java code to compute Fibonacci numbers recursively?

DSA Java

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

A StackOverflowError

B Output is 3

C Output is 5

D Compilation error

💡 Hint

Check the recursive calls and see if they always reduce n properly.

The recursive call fib(n - 3) can cause negative arguments for n < 3, leading to infinite recursion and eventually StackOverflowError.

❓ Predict Output

advanced

Output of Memoized Fibonacci Code

What is the output of this Java code that uses memoization to compute Fibonacci numbers?

DSA Java

import java.util.HashMap;
public class Fibonacci {
    static HashMap<Integer, Integer> memo = new HashMap<>();
    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }
    public static void main(String[] args) {
        for (int i = 0; i < 7; i++) {
            System.out.print(fib(i) + " ");
        }
    }
}

A 1 2 3 5 8 13 21

B 1 1 2 3 5 8 13

C 0 1 2 3 5 8 13

D 0 1 1 2 3 5 8

💡 Hint

Memoization stores results to avoid repeated calculations.

The memoized fib function returns correct Fibonacci numbers starting from 0,1,... up to fib(6) = 8.

🧠 Conceptual

expert

Time Complexity of Recursive Fibonacci Without Memoization

What is the time complexity of the naive recursive Fibonacci function without memoization?

A O(2^n)

B O(n)

C O(n^2)

D O(log n)

💡 Hint

Consider how many calls are made as n increases.

Each call to fib(n) makes two calls to fib(n-1) and fib(n-2), leading to exponential growth in calls, so time complexity is O(2^n).

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