Why Recursion Base Case and Recursive Case in DSA C#?

The Big Idea

Discover how a simple stop rule can turn a huge problem into tiny, easy steps!

The Scenario

Imagine you want to find the total number of steps to climb a tall staircase by counting each step one by one manually.

You start at the bottom and try to count all steps without losing track.

The Problem

Counting each step manually is slow and easy to mess up, especially if the staircase is very tall.

You might lose count or forget where you left off, making the process frustrating and error-prone.

The Solution

Recursion breaks the problem into smaller, similar problems.

It uses a simple stopping point (base case) to stop counting and a rule (recursive case) to keep counting step by step automatically.

Before vs After

✗ Before

int CountSteps(int steps) {
    int total = 0;
    for (int i = 1; i <= steps; i++) {
        total++;
    }
    return total;
}

✓ After

int CountSteps(int steps) {
    if (steps == 0) return 0;  // base case
    return 1 + CountSteps(steps - 1);  // recursive case
}

What It Enables

Recursion allows solving big problems by solving smaller parts automatically and clearly.

Real Life Example

When you want to open nested boxes inside boxes, recursion helps by opening one box at a time until you reach the last box.

Key Takeaways

Base case stops the recursion to avoid endless loops.

Recursive case breaks the problem into smaller parts.

Together, they make complex problems easier to solve step-by-step.

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