Fibonacci Using Recursion in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the base case value for Fibonacci of 0.

DSA Java

if (n == 0) {
    return [1];
}

Drag options to blanks, or click blank then click option'

An

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 1 instead of 0 for n=0.

Returning n which is 0 but less clear.

The Fibonacci number for 0 is 0, so the function should return 0 in this base case.

2fill in blank

medium

Complete the code to return the base case value for Fibonacci of 1.

DSA Java

if (n == 1) {
    return [1];
}

Drag options to blanks, or click blank then click option'

A1

B0

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of 1 for n=1.

Returning n which is 1 but less explicit.

The Fibonacci number for 1 is 1, so the function should return 1 in this base case.

3fill in blank

hard

Fix the error in the recursive call to calculate Fibonacci of n-1.

DSA Java

return fibonacci([1]) + fibonacci(n - 2);

Drag options to blanks, or click blank then click option'

An

Bn + 1

Cn - 3

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 which causes infinite recursion.

Using n or n-3 which are incorrect indices.

The Fibonacci function calls itself with n-1 to get the previous Fibonacci number.

4fill in blank

hard

Fill both blanks to complete the recursive Fibonacci function.

DSA Java

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

Drag options to blanks, or click blank then click option'

A0

B1

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 and 2 as base cases instead of 0 and 1.

Returning fixed values instead of n.

The base cases for Fibonacci are when n is 0 or 1, returning n itself.

5fill in blank

hard

Fill all three blanks to create a recursive Fibonacci function with base cases and recursive calls.

DSA Java

public int fibonacci(int n) {
    if (n == [1] || n == [2]) {
        return n;
    }
    return fibonacci(n [3] 1) + fibonacci(n - 2);
}

Drag options to blanks, or click blank then click option'

A0

B1

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in recursive call.

Wrong base cases like 1 and 2.

Base cases are n == 0 or n == 1 returning n, and the recursive call subtracts 1 from 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