Fibonacci Using Recursion in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the base case value for n equals 0 in the Fibonacci function.

DSA C++

int fibonacci(int n) {
    if (n == 0) {
        return [1];
    }
    // other code
}

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

A0

B1

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 1 instead of 0 for n=0

Returning n directly without checking base case

The Fibonacci sequence starts with 0 for n=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 n equals 1 in the Fibonacci function.

DSA C++

int fibonacci(int n) {
    if (n == 1) {
        return [1];
    }
    // other code
}

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

A0

B1

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of 1 for n=1

Not handling the base case for n=1

The Fibonacci sequence has 1 as the value for n=1, so the function should return 1 in this base case.

3fill in blank

hard

Fix the error in the recursive call to compute the Fibonacci number for n-1.

DSA C++

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

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

An + 1

Bn - 2

Cn - 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 which causes infinite recursion

Using n or n-2 incorrectly in the first recursive call

The Fibonacci number for n is the sum of Fibonacci(n-1) and Fibonacci(n-2). The recursive call must use n-1.

4fill in blank

hard

Fill both blanks to complete the recursive Fibonacci function correctly.

DSA C++

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

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

An - 1

Bn - 2

Cn + 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 or n instead of n-1 or n-2

Swapping the order of n-1 and n-2 (though order doesn't affect result)

The Fibonacci function returns the sum of fibonacci(n-1) and fibonacci(n-2) for n > 1.

5fill in blank

hard

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

DSA C++

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

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

A0

B1

Cn - 1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong base case values

Incorrect recursive call argument

The base cases are for n=0 and n=1, returning n. The recursive call uses n-1 and n-2.

Practice

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

easy

A. Each number is the square of the previous number

B. Each number is the sum of the two preceding numbers starting from 0 and 1

C. Each number is the difference between the two preceding numbers

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

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two 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 starting from 0 and 1 -> Option B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds last two numbers recursively [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or squares with Fibonacci
• Ignoring the base cases 0 and 1

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

easy

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

B. if (n <= 2) return n;

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

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

Solution

1. Step 1: Identify correct Fibonacci base cases

   Fibonacci sequence starts with 0 at position 0 and 1 at position 1, so base cases must return these values.

2. Step 2: Match base cases to code

   if (n == 0) return 0; if (n == 1) return 1; correctly returns 0 for n=0 and 1 for n=1, matching Fibonacci definition.

3. Final Answer:

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

4. Quick Check:

   Base cases match Fibonacci start [OK]

Hint: Base cases: 0 returns 0, 1 returns 1 [OK]

Common Mistakes:

• Using wrong base values like 1 for n=0
• Returning n for n <= 2 which is incorrect
• Confusing base cases with general recursive step

3. What is the output of the following C++ code?

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

int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

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

   fib(5) = fib(4) + fib(3). Calculate fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), and so on until base cases.

2. Step 2: Evaluate values step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Calculating fib(5) as 8 or 13 by mistake
• Confusing index starting point
• Skipping base cases in calculation

4. Identify the error in this recursive Fibonacci function:

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

medium

A. No error, function is correct

B. The recursive calls are in wrong order; should be fib(n-1) + fib(n-2)

C. Base cases are incorrect

D. Missing return type in function

Solution

1. Step 1: Check base cases

   Base cases for n==0 return 0 and n==1 return 1 are correct for Fibonacci.

2. Step 2: Check recursive step

   fib(n-2) + fib(n-1) equals fib(n-1) + fib(n-2) because addition is commutative. Function computes correct values. No error.

3. Final Answer:

   No error, function is correct -> Option A

4. Quick Check:

   Addition commutative, no error [OK]

Hint: Addition order irrelevant, commutative [OK]

Common Mistakes:

• Thinking recursive call order must be strictly n-1 first
• Assuming reversed order changes the result
• Overlooking commutativity of addition

5. How many times is the function fib called when computing fib(4) using the recursive function below?

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

hard

A. 5

B. 7

C. 15

D. 9

Solution

1. Step 1: Trace calls for fib(4)

   fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0).

2. Step 2: Count total calls

   Calls: fib(4), fib(3), fib(2), fib(1), fib(2), fib(1), fib(0), fib(1), fib(0) = 9 calls total.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Count recursive calls carefully = 9 [OK]

Hint: Count each fib call including duplicates [OK]

Common Mistakes:

• Counting only unique calls
• Ignoring repeated calls for same n
• Underestimating recursion tree size