Recursion Base Case and Recursive Case in DSA C# - Time & Space Complexity

Time Complexity: Recursion Base Case and Recursive Case

O(n)

Understanding Time Complexity

We want to understand how the time taken by a recursive function grows as the input size increases.

Specifically, how the base case and recursive calls affect the total work done.

Scenario Under Consideration

Analyze the time complexity of the following recursive function.

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

This function calculates the factorial of n by calling itself with smaller values until it reaches zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One recursive call per function call.
• How many times: The function calls itself n times until reaching the base case.

How Execution Grows With Input

Each call does a small amount of work and then calls itself with n-1.

Input Size (n)	Approx. Operations
10	About 11 calls
100	About 101 calls
1000	About 1001 calls

Pattern observation: The number of calls grows directly with n, so the work grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in a straight line as the input number increases.

Common Mistake

[X] Wrong: "Recursion always means exponential time because it calls itself multiple times."

[OK] Correct: Here, the function calls itself only once per call, so the total calls grow linearly, not exponentially.

Interview Connect

Understanding how base and recursive cases affect time helps you explain and analyze recursive solutions clearly in interviews.

Self-Check

"What if the function made two recursive calls instead of one? How would the time complexity change?"

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