Recursion Base Case and Recursive Case in DSA C#

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine stacking boxes inside bigger boxes. You keep opening the next smaller box until you find the smallest box that you can open without any more boxes inside.

Call stack:
main -> func(3) -> func(2) -> func(1) -> base case reached
Each arrow means a function calling itself with a smaller number.

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down into smaller factorials until reaching 1

Step 1: Call factorial(3), not base case, so call factorial(2)

Call stack: main -> factorial(3) ↑ waiting for factorial(2)

Why: We reduce the problem to a smaller one to solve it step by step

Step 2: Call factorial(2), not base case, so call factorial(1)

Call stack: main -> factorial(3) -> factorial(2) ↑ waiting for factorial(1)

Why: Keep breaking down until we reach the simplest case

Step 3: Call factorial(1), base case reached, return 1

Call stack: main -> factorial(3) -> factorial(2) -> factorial(1) ↑ returns 1

Why: Base case stops recursion and starts returning answers

Step 4: Return factorial(2) = 2 x factorial(1) = 2 x 1 = 2

Call stack: main -> factorial(3) -> factorial(2) ↑ returns 2

Why: Combine smaller answers to build the bigger answer

Step 5: Return factorial(3) = 3 x factorial(2) = 3 x 2 = 6

Call stack: main -> factorial(3) ↑ returns 6

Why: Final answer is built by combining all smaller answers

Result:

Final result: factorial(3) = 6

Annotated Code

DSA C#

using System;

class Program
{
    // Recursive function to calculate factorial
    static int Factorial(int n)
    {
        if (n == 1) // base case
            return 1;
        return n * Factorial(n - 1); // recursive case
    }

    static void Main()
    {
        int number = 3;
        int result = Factorial(number);
        Console.WriteLine($"Factorial of {number} is {result}");
    }
}

if (n == 1) // base case

stop recursion when simplest case reached

return n * Factorial(n - 1); // recursive case

call function with smaller input to build answer

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) due to the call stack holding n function calls at once

vs Alternative: Iterative approach uses O(1) space but recursion is easier to write and understand for problems like factorial

Edge Cases

Input is 1 (smallest valid input)

Function returns 1 immediately without further calls

DSA C#

if (n == 1) // base case

Input is 0 or negative (not handled in this code)

Function will recurse infinitely or cause error; needs input validation

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a simple stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Missing or incorrect base case causing infinite recursion
Fix: Add a correct base case that stops recursion for the simplest input

Mistake: Calling recursive function without reducing input leading to no progress
Fix: Ensure recursive call uses a smaller or simpler input to move toward base case

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems with a clear stopping point.

The key is to have a base case that stops recursion and a recursive case that reduces the problem size.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To print the result of the recursion

B. To call the function again with a smaller input

C. To stop the recursion and prevent infinite calls

D. To increase the input size for the next call

Solution

1. Step 1: Understand the role of base case

   The base case is the condition where the recursion stops to avoid infinite calls.

2. Step 2: Differentiate base case from recursive case

   The recursive case calls the function again, but the base case returns a value without further calls.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option C

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid endless loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls function again
• Ignoring base case leads to infinite recursion

2. Which of the following is the correct syntax for a base case in this C# recursive function to calculate factorial?

int Factorial(int n) {
    if (___) return 1;
    return n * Factorial(n - 1);
}

easy

A. n == 0

B. n > 0

C. n < 0

D. n == 1

Solution

1. Step 1: Identify the base case for factorial

   Factorial of 0 is defined as 1, so base case is when n == 0.

2. Step 2: Check options for correct base case condition

   Only 'n == 0' correctly stops recursion and returns 1.

3. Final Answer:

   n == 0 -> Option A

4. Quick Check:

   Factorial base case = n == 0 [OK]

Hint: Factorial base case is n equals zero [OK]

Common Mistakes:

• Using n > 0 as base case causes infinite recursion
• Using n == 1 misses factorial(0) definition
• Using n < 0 causes wrong behavior

3. What will be the output of this C# code?

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

Console.WriteLine(Sum(3));

medium

A. 6

B. 3

C. 0

D. Error

Solution

1. Step 1: Trace recursive calls for Sum(3)

   Sum(3) = 3 + Sum(2), Sum(2) = 2 + Sum(1), Sum(1) = 1 + Sum(0), Sum(0) = 0.

2. Step 2: Calculate return values step-by-step

   Sum(0) = 0, Sum(1) = 1 + 0 = 1, Sum(2) = 2 + 1 = 3, Sum(3) = 3 + 3 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

Hint: Sum from n to 0 adds all numbers [OK]

Common Mistakes:

• Confusing base case return value
• Adding n instead of subtracting in recursive call
• Expecting output as input value

4. Identify the error in this recursive function to find factorial:

int Factorial(int n) {
    if (n == 1) return 1;
    else return n * Factorial(n + 1);
}

medium

A. Missing else block causes syntax error

B. Base case should be n == 0, not n == 1

C. Function should return void, not int

D. Recursive call should use n - 1, not n + 1

Solution

1. Step 1: Analyze recursive call parameter

   The function calls Factorial(n + 1), which increases n, causing infinite recursion.

2. Step 2: Correct recursive call for factorial

   Factorial should call Factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call should use n - 1, not n + 1 -> Option D

4. Quick Check:

   Factorial recursion decreases n [OK]

Hint: Recursive call must reduce input to reach base case [OK]

Common Mistakes:

• Increasing n causes infinite recursion
• Confusing base case condition
• Thinking else block is mandatory

5. You want to write a recursive function in C# to reverse a string. Which base case and recursive case are correct?

string Reverse(string s) {
    if (___) return ___;
    return Reverse(___) + s[0];
}

hard

A. s.Length == 1; ""; s.Substring(1)

B. s.Length == 0; s; s.Substring(1)

C. s.Length == 1; s; s.Substring(0, s.Length - 1)

D. s == null; null; s.Substring(1)

Solution

1. Step 1: Identify base case for empty string

   When string length is 0, return the string itself (empty string).

2. Step 2: Understand recursive case for reversing

   Call Reverse on substring from index 1 to end, then add first character at the end.

3. Final Answer:

   s.Length == 0; s; s.Substring(1) -> Option B

4. Quick Check:

   Empty string base case, substring recursive call [OK]

Hint: Base case empty string; recursive call on substring from index 1 [OK]

Common Mistakes:

• Using s == null instead of empty string
• Wrong substring indices causing errors
• Returning s instead of empty string in base case