Fibonacci Using Recursion in DSA C++ - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You are helping a friend understand how to calculate Fibonacci numbers using a simple recursive function. Fibonacci numbers are a sequence where each number is the sum of the two before it, starting with 0 and 1.

🎯 Goal: Build a C++ program that uses a recursive function to find the Fibonacci number at a given position.

📋 What You'll Learn

Create a recursive function called fibonacci that takes an integer n and returns the Fibonacci number at position n.

Use base cases for n == 0 and n == 1 to return 0 and 1 respectively.

Call the fibonacci function with n = 6 and store the result in a variable called result.

Print the value of result.

💡 Why This Matters

🌍 Real World

Fibonacci numbers appear in nature, computer algorithms, and financial models. Understanding recursion helps solve problems that can be broken down into smaller similar problems.

💼 Career

Recursion is a fundamental programming concept used in many technical interviews and real-world software development tasks involving trees, graphs, and divide-and-conquer algorithms.

1

Create the Fibonacci function signature

Write the function signature for a recursive function called fibonacci that takes an integer parameter n and returns an integer.

DSA C++

// Write the function signature for fibonacci
// Your code here

Hint

Start by writing the function header only, without the body.

2

Add base cases for recursion

Inside the fibonacci function, add base cases to return 0 when n == 0 and return 1 when n == 1.

DSA C++

int fibonacci(int n) {
    // Add base cases for n == 0 and n == 1
    // Your code here
}

Hint

Use two if statements to check for n == 0 and n == 1 and return the correct values.

3

Add recursive call to calculate Fibonacci

Complete the fibonacci function by returning the sum of fibonacci(n - 1) and fibonacci(n - 2) for other values of n.

DSA C++

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    // Return sum of fibonacci(n - 1) and fibonacci(n - 2)
    // Your code here
}

Hint

Use the function name fibonacci recursively with n - 1 and n - 2 and add their results.

4

Call the function and print the result

In the main function, call fibonacci with 6, store the result in a variable called result, and print result.

DSA C++

#include 

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

int main() {
    // Call fibonacci(6), store in result, and print result
    // Your code here
    return 0;
}

Hint

Use int result = fibonacci(6); and then std::cout << result << std::endl; to print.

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