Recursion Base Case and Recursive Case in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in recursion?

The base case is the condition that stops the recursion. It prevents infinite calls by providing a simple answer without further recursion.

beginner

What is the recursive case in recursion?

The recursive case is where the function calls itself with a smaller or simpler input, moving towards the base case.

beginner

Why do we need both base case and recursive case in a recursive function?

The base case stops the recursion to avoid infinite loops, and the recursive case breaks the problem into smaller parts to solve it step by step.

intermediate

Consider this C# recursive function snippet:

int Factorial(int n) {
  if (n == 0) return 1;  // base case
  return n * Factorial(n - 1);  // recursive case
}

What are the base case and recursive case here?

Base case: if (n == 0) return 1; stops recursion.
Recursive case: return n * Factorial(n - 1); calls itself with smaller input.

beginner

What happens if a recursive function has no base case?

The function will keep calling itself forever, causing a stack overflow error because it never stops.

What is the purpose of the base case in recursion?

A To print the result

B To call the function again with a smaller input

C To stop the recursion and return a result

D To increase the input size

The base case stops the recursion by returning a result without further calls.

In the recursive case, what does the function usually do?

A Calls itself with a simpler or smaller input

B Returns a fixed value

C Ends the program

D Prints the input

The recursive case calls the function itself with a smaller input to approach the base case.

What will happen if a recursive function lacks a base case?

A It will print an error message

B It will return immediately

C It will run only once

D It will run forever and cause a stack overflow

Without a base case, recursion never stops, causing a stack overflow error.

In this code snippet, what is the base case?

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

A if (n == 0) return 0;

B return n + Sum(n - 1);

C int Sum(int n)

D return 0;

The base case is the condition that stops recursion: if n is 0, return 0.

Which of these is NOT true about recursion?

A Every recursive function must have a base case

B Recursion always uses loops internally

C Recursive case breaks the problem into smaller parts

D Without a base case, recursion causes errors

Recursion does not always use loops; it uses function calls to itself.

Explain in your own words what the base case and recursive case are in recursion.

Think about how recursion stops and how it continues.

Describe what would happen if a recursive function does not have a base case.

Imagine a function calling itself forever without stopping.

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