Recursion Base Case and Recursive Case in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of the following C# code when calling Factorial(4)?

DSA C#

using System;
class Program {
  static int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
  }
  static void Main() {
    Console.WriteLine(Factorial(4));
  }
}

A 120

B 24

C 0

D 10

💡 Hint

Remember factorial of 0 is 1 and factorial(n) = n * factorial(n-1).

The function calculates factorial recursively. Factorial(4) = 4 * 3 * 2 * 1 = 24.

❓ Predict Output

intermediate

Output of Recursive Sum Function

What is printed when the following C# code runs with Sum(3)?

DSA C#

using System;
class Program {
  static int Sum(int n) {
    if (n <= 0) return 0;
    return n + Sum(n - 1);
  }
  static void Main() {
    Console.WriteLine(Sum(3));
  }
}

A 6

B 3

C 0

D 9

💡 Hint

Sum(n) adds n to Sum(n-1) until n is 0 or less.

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

❓ Predict Output

advanced

Output of Recursive String Reverse

What is the output of this C# program when calling Reverse("abc")?

DSA C#

using System;
class Program {
  static string Reverse(string s) {
    if (s.Length == 0) return "";
    return Reverse(s.Substring(1)) + s[0];
  }
  static void Main() {
    Console.WriteLine(Reverse("abc"));
  }
}

A abc

B acb

C Error

D cba

💡 Hint

The function moves the first character to the end recursively.

The function reverses the string by calling itself on the substring without the first character, then appending the first character at the end.

❓ Predict Output

advanced

Output of Recursive Fibonacci Function

What does the following C# code print when calling Fibonacci(5)?

DSA C#

using System;
class Program {
  static int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }
  static void Main() {
    Console.WriteLine(Fibonacci(5));
  }
}

A 5

B 3

C 8

D 13

💡 Hint

Fibonacci sequence starts 0,1,1,2,3,5,...

Fibonacci(5) = Fibonacci(4) + Fibonacci(3) = 3 + 2 = 5.

🧠 Conceptual

expert

Identifying Base Case in Recursive Function

Which of the following is the correct base case for a recursive function that calculates the sum of numbers from 1 to n?

A if (n < 0) return 0;

B if (n == 1) return 1;

C if (n == 0) return 0;

D if (n == 2) return 2;

💡 Hint

Think about the smallest input where recursion should stop.

The base case for sum from 1 to n is when n is 0, returning 0 stops recursion correctly.

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