Fibonacci Using Recursion in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in a recursive Fibonacci function?

The base case returns the first two Fibonacci numbers directly: fib(0) = 0 and fib(1) = 1. This stops the recursion from continuing infinitely.

beginner

Explain how recursion works in the Fibonacci sequence calculation.

Recursion breaks the problem into smaller parts by calling the Fibonacci function for (n-1) and (n-2), then adds their results to get fib(n). This repeats until it reaches the base cases.

intermediate

What is the time complexity of the naive recursive Fibonacci algorithm?

The time complexity is exponential, specifically O(2^n), because it recalculates the same Fibonacci numbers many times.

intermediate

Why does the naive recursive Fibonacci function have poor performance?

Because it repeats calculations for the same inputs multiple times without saving results, leading to many redundant calls.

beginner

Write the recursive formula used in Fibonacci sequence.

fib(n) = fib(n-1) + fib(n-2) with base cases fib(0) = 0 and fib(1) = 1.

What does the base case in a recursive Fibonacci function do?

A Adds two previous Fibonacci numbers

B Calls the function again with smaller inputs

C Stops recursion by returning known values

D Calculates Fibonacci iteratively

The base case stops recursion by returning known Fibonacci numbers for fib(0) and fib(1).

Which two previous Fibonacci numbers are added to get fib(n)?

A fib(n-1) and fib(n-2)

B fib(n-1) and fib(n-3)

C fib(n) and fib(n-1)

D fib(n-2) and fib(n-3)

fib(n) is calculated by adding fib(n-1) and fib(n-2).

What is the main drawback of the naive recursive Fibonacci method?

A Has exponential time complexity

B Uses too much memory

C Does not return correct results

D Requires iterative loops

The naive recursive method has exponential time complexity due to repeated calculations.

What is the output of fib(3) using recursion?

A 3

B 2

C 1

D 5

fib(3) = fib(2) + fib(1) = 1 + 1 = 2.

Which of these is NOT a base case for Fibonacci recursion?

A fib(0) = 0

B fib(1) = 1

C fib(2) = 1

D fib(3) = 2

Only fib(0) and fib(1) are base cases; fib(3) is calculated recursively.

Describe how a recursive function calculates the Fibonacci number for n.

Think about how the function calls itself with smaller numbers until it reaches the simplest cases.

Explain why the naive recursive Fibonacci algorithm is inefficient and how it can be improved.

Consider what happens when the function calculates the same Fibonacci number multiple times.

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