Fibonacci Using Recursion in DSA C#

Mental Model

Calculate each Fibonacci number by adding the two before it, using a function that calls itself.

Analogy: Like climbing stairs where to reach step n, you first need to know how you got to steps n-1 and n-2.

fib(4)
  /    \
fib(3)  fib(2)
 /  \    /  \
fib(2) fib(1) fib(1) fib(0)
 /  \
fib(1) fib(0)

Dry Run Walkthrough

Input: Calculate fib(4) using recursion

Goal: Find the 4th Fibonacci number by breaking it down into smaller Fibonacci calls

Step 1: Call fib(4), which calls fib(3) and fib(2)

fib(4) -> fib(3), fib(2)

Why: To find fib(4), we need fib(3) and fib(2)

Step 2: Call fib(3), which calls fib(2) and fib(1)

fib(3) -> fib(2), fib(1); fib(2) pending

Why: fib(3) depends on fib(2) and fib(1)

Step 3: Call fib(2), which calls fib(1) and fib(0)

fib(2) -> fib(1), fib(0); fib(1), fib(0) are base cases

Why: fib(2) breaks down to base cases fib(1) and fib(0)

Step 4: Return fib(1) = 1 and fib(0) = 0, so fib(2) = 1 + 0 = 1

fib(2) = 1

Why: Base cases return fixed values

Step 5: Return fib(1) = 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2

fib(3) = 2

Why: Combine results to get fib(3)

Step 6: Return fib(2) = 1 from earlier call

fib(2) = 1

Why: fib(2) was already calculated

Step 7: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3

fib(4) = 3

Why: Final result combines fib(3) and fib(2)

Result:

fib(4) = 3

Annotated Code

DSA C#

using System;

class Fibonacci {
    public static int Fib(int n) {
        if (n == 0) return 0; // base case 0
        if (n == 1) return 1; // base case 1
        return Fib(n - 1) + Fib(n - 2); // recursive call
    }

    static void Main() {
        int n = 4;
        int result = Fib(n);
        Console.WriteLine($"fib({n}) = {result}");
    }
}

if (n == 0) return 0; // base case 0

return 0 when n is 0 to stop recursion

if (n == 1) return 1; // base case 1

return 1 when n is 1 to stop recursion

return Fib(n - 1) + Fib(n - 2); // recursive call

calculate fib(n) by adding fib(n-1) and fib(n-2)

Output

fib(4) = 3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, doubling work

Space: O(n) due to call stack depth from recursion

vs Alternative: Iterative approach is O(n) time and O(1) space, much faster and uses less memory

Edge Cases

n = 0

Returns 0 immediately as base case

DSA C#

if (n == 0) return 0; // base case 0

n = 1

Returns 1 immediately as base case

DSA C#

if (n == 1) return 1; // base case 1

negative n

No guard, will cause infinite recursion or stack overflow

DSA C#

No explicit guard in code

When to Use This Pattern

When a problem asks for a sequence where each value depends on previous two, use recursion to break it down into smaller subproblems.

Common Mistakes

Mistake: Missing base cases causing infinite recursion
Fix: Add base cases for n == 0 and n == 1 to stop recursion

Mistake: Calling Fib(n-1) and Fib(n-2) without return causing no result
Fix: Return the sum of Fib(n-1) and Fib(n-2) to propagate result up

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to find Fibonacci numbers but input size is small.

The key is to stop recursion with base cases and combine smaller results to build the answer.

Practice

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

easy

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

B. Each number is the sum of the two preceding numbers

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

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

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: Apply to recursion context

   Recursion calculates this by calling the function for the two previous numbers and adding their results.

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: Remember Fibonacci adds two previous numbers [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or division with addition
• Assuming Fibonacci uses only one previous number

2. Which of the following is the correct C# syntax to define a recursive Fibonacci function header?

easy

A. void Fibonacci(int n)

B. int Fibonacci()

C. int Fibonacci(int n)

D. int Fibonacci(int)

Solution

1. Step 1: Identify function return type and parameters

   The Fibonacci function returns an integer and takes an integer parameter for the position.

2. Step 2: Match correct C# syntax

   Correct syntax includes return type, function name, and parameter with type: int Fibonacci(int n)

3. Final Answer:

   int Fibonacci(int n) -> Option C

4. Quick Check:

   Function returns int and takes int parameter [OK]

Hint: Function must return int and take int parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing parameter type or name
• Incorrect parameter list syntax

3. What is the output of this C# code snippet?

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

Console.WriteLine(Fibonacci(4));

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Calculate Fibonacci(4) using recursion

   Fibonacci(4) = Fibonacci(3) + Fibonacci(2). Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 1 + 1 = 2. Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = 1 + 0 = 1. So Fibonacci(4) = 2 + 1 = 3.

2. Step 2: Confirm output

   The printed output is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Trace calls down to base cases to sum results [OK]

Common Mistakes:

• Confusing Fibonacci(4) with Fibonacci(5)
• Miscounting base cases
• Adding wrong recursive results

4. Identify the error in this recursive Fibonacci function:

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

medium

A. The recursive call uses subtraction instead of addition

B. Parameter type is missing

C. Function lacks return type

D. Base cases are incorrect

Solution

1. Step 1: Check base cases

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

2. Step 2: Analyze recursive return statement

   The function uses subtraction (Fibonacci(n - 1) - Fibonacci(n - 2)) instead of addition, which is incorrect for Fibonacci sequence.

3. Final Answer:

   The recursive call uses subtraction instead of addition -> Option A

4. Quick Check:

   Fibonacci sums previous two, not subtracts [OK]

Hint: Fibonacci adds two previous calls, not subtracts [OK]

Common Mistakes:

• Using subtraction instead of addition in recursion
• Forgetting to return in base cases
• Missing parameter or return type in function

5. How can you optimize the recursive Fibonacci function to avoid repeated calculations?

hard

A. Increase the recursion depth limit

B. Replace recursion with a while loop only

C. Use subtraction instead of addition in recursion

D. Use memoization to store and reuse computed values

Solution

1. Step 1: Understand problem with naive recursion

   Naive recursion recalculates Fibonacci values many times, causing inefficiency.

2. Step 2: Apply memoization technique

   Memoization stores results of Fibonacci calls in a cache to reuse, avoiding repeated work.

3. Final Answer:

   Use memoization to store and reuse computed values -> Option D

4. Quick Check:

   Memoization optimizes recursion by caching results [OK]

Hint: Cache results to avoid repeated recursive calls [OK]

Common Mistakes:

• Thinking only loops can optimize recursion
• Increasing recursion depth does not improve efficiency
• Using subtraction breaks Fibonacci logic