Fibonacci Using Recursion in DSA Java

Mental Model

Calculate each Fibonacci number by adding the two before it, using a function that calls itself.

Analogy: Like climbing stairs where to reach step n, you first need to know how to reach steps n-1 and n-2.

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

Dry Run Walkthrough

Input: Calculate fib(4)

Goal: Find the 4th Fibonacci number using recursion

Step 1: Call fib(4), which calls fib(3) and fib(2)

fib(4) -> fib(3) + fib(2)

Why: fib(4) depends on fib(3) and fib(2) to calculate its value

Step 2: Call fib(3), which calls fib(2) and fib(1)

fib(3) -> fib(2) + fib(1)

Why: fib(3) depends on fib(2) and fib(1)

Step 3: Call fib(2), which calls fib(1) and fib(0)

fib(2) -> fib(1) + fib(0)

Why: fib(2) depends on fib(1) and fib(0)

Step 4: fib(1) returns 1 and fib(0) returns 0, so fib(2) = 1 + 0 = 1

fib(2) = 1

Why: Base cases return fixed values to stop recursion

Step 5: fib(1) returns 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2

fib(3) = 2

Why: Combine results of fib(2) and fib(1) to get fib(3)

Step 6: fib(2) calls fib(1) and fib(0) again, returns 1

fib(2) = 1

Why: fib(2) calculation repeats for fib(4) calculation

Step 7: fib(4) = fib(3) + fib(2) = 2 + 1 = 3

fib(4) = 3

Why: Final sum of fib(3) and fib(2) gives fib(4)

Result:

fib(4) = 3

Annotated Code

DSA Java

public class FibonacciRecursive {
    // Calculate Fibonacci number using recursion
    public static int fib(int n) {
        if (n == 0) return 0; // base case 0
        if (n == 1) return 1; // base case 1
        return fib(n - 1) + fib(n - 2); // recursive call
    }

    public static void main(String[] args) {
        int n = 4;
        int result = fib(n);
        System.out.println("fib(" + n + ") = " + result);
    }
}

if (n == 0) return 0; // base case 0

stop recursion when n is 0

if (n == 1) return 1; // base case 1

stop recursion when n is 1

return fib(n - 1) + fib(n - 2); // recursive call

calculate fib(n) by summing fib(n-1) and fib(n-2)

Output

fib(4) = 3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, doubling work

Space: O(n) due to the maximum depth of the recursion call stack

vs Alternative: Iterative approach is O(n) time and O(1) space, much more efficient than recursive

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Java

if (n == 0) return 0; // base case 0

n = 1

Returns 1 immediately as base case

DSA Java

if (n == 1) return 1; // base case 1

negative n

No guard, will cause infinite recursion or stack overflow

DSA Java

No explicit guard for negative input

When to Use This Pattern

When you see a problem asking for a sequence where each value depends on previous two, try recursion with base cases to break down the problem.

Common Mistakes

Mistake: Missing base cases causing infinite recursion
Fix: Add conditions to return fixed values for n=0 and n=1

Mistake: Calling fib(n-1) and fib(n-2) without returning their sum
Fix: Return the sum of fib(n-1) and fib(n-2) to get correct result

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to find Fibonacci numbers for small n.

The key is to stop recursion at base cases and combine smaller results.

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