Why Fibonacci Using Recursion in DSA C++?

The Big Idea

Discover how a simple function can solve a complex pattern by calling itself!

The Scenario

Imagine you want to find the 10th number in the Fibonacci sequence by writing down each number one by one on paper.

You start adding the last two numbers repeatedly to get the next one.

The Problem

Doing this by hand is slow and easy to make mistakes, especially as the numbers get bigger.

It's hard to keep track of all the additions and remember previous numbers without error.

The Solution

Using recursion, the computer can automatically break down the problem into smaller parts.

It calculates smaller Fibonacci numbers first and then combines them to get the bigger ones, without you having to track each step manually.

Before vs After

✗ Before

int fibonacci(int n) {
  if (n <= 1) return n;
  int a = 0, b = 1, c;
  for (int i = 2; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return b;
}

✓ After

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

What It Enables

This lets us solve complex problems by breaking them into simpler, repeatable steps that the computer handles automatically.

Real Life Example

Calculating Fibonacci numbers is useful in computer graphics, financial models, and nature simulations where patterns repeat in a similar way.

Key Takeaways

Manual calculation is slow and error-prone.

Recursion breaks the problem into smaller, manageable parts.

It helps automate repetitive calculations efficiently.

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