Recursion Concept and Call Stack Visualization 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 24

B 10

C 1

D 120

💡 Hint

Recall that factorial of n is n multiplied by factorial of n-1, with factorial of 0 as 1.

The factorial of 4 is 4 * 3 * 2 * 1 = 24. The recursion multiplies down to 1.

❓ Predict Output

intermediate

Output of Recursive Fibonacci Function

What is printed when the following C# program runs 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 13

B 8

C 5

D 3

💡 Hint

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

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

🔧 Debug

advanced

Identify the Error in Recursive Sum Function

What error occurs when running this C# code that sums numbers from n down to 1 recursively?

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 No error, outputs 6

B ArgumentException

C NullReferenceException

D StackOverflowException

💡 Hint

Check if the recursive call reduces the problem size.

The original code caused infinite recursion because the recursive call did not reduce n. The fixed code reduces n by 1 each call, so it terminates correctly.

🧠 Conceptual

advanced

Call Stack Depth for Recursive Function

If a recursive function calls itself with n-1 until n == 0, what is the maximum call stack depth when called with n = 7?

A 7

B 8

C 6

D 1

💡 Hint

Count the initial call plus each recursive call until base case.

The function calls itself 7 times plus the initial call, totaling 8 calls on the stack.

🚀 Application

expert

Output of Recursive String Reversal

What is the output of this C# program that reverses a string recursively when input is "code"?

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("code"));
  }
}

A oced

B code

C edco

D edoc

💡 Hint

The function moves the first character to the end after reversing the rest.

The recursion reverses the substring from index 1 onward, then adds the first character at the end, effectively reversing the string.

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It runs only once and stops

B. It immediately returns without doing anything

C. It causes an infinite loop leading to a stack overflow error

D. It converts into a normal loop automatically

Solution

1. Step 1: Understand recursion stopping condition

   A recursive function must have a base case to stop calling itself; otherwise, it keeps calling endlessly.

2. Step 2: Effect of missing base case

   Without a base case, the function calls stack up until memory runs out, causing a stack overflow error.

3. Final Answer:

   It causes an infinite loop leading to a stack overflow error -> Option C

4. Quick Check:

   Missing base case = infinite recursion [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Assuming recursion stops automatically
• Confusing recursion with loops
• Thinking recursion runs only once without base case

2. Which of the following is the correct syntax to define a recursive method in C# that calculates factorial?

easy

A. int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); }

B. int Factorial(int n) { while (n > 0) return n * Factorial(n - 1); return 1; }

C. int Factorial(int n) { if (n == 1) return 0; else return n + Factorial(n - 1); }

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

Solution

1. Step 1: Check base case correctness

   Factorial base case is when n == 0, return 1; this matches int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } only.

2. Step 2: Check recursive call correctness

   Recursive call must reduce n by 1 and multiply; int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } does this correctly.

3. Final Answer:

   int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } -> Option A

4. Quick Check:

   Base case n==0 and n*Factorial(n-1) [OK]

Hint: Base case returns 1; recursive call multiplies by n-1 factorial [OK]

Common Mistakes:

• Using wrong base case value
• Increasing n instead of decreasing
• Returning 0 instead of 1 in base case

3. What is the output of the following C# code?

static void PrintNumbers(int n) {
  if (n == 0) return;
  Console.Write(n + " ");
  PrintNumbers(n - 1);
}

PrintNumbers(3);

medium

A. 1 2 3

B. 0 1 2 3

C. 3 2 1 0

D. 3 2 1

Solution

1. Step 1: Trace the recursive calls

   PrintNumbers(3) prints 3, then calls PrintNumbers(2), prints 2, calls PrintNumbers(1), prints 1, then calls PrintNumbers(0) which returns.

2. Step 2: Collect printed output

   Printed numbers are 3, 2, 1 in that order, each followed by a space.

3. Final Answer:

   3 2 1 -> Option D

4. Quick Check:

   Print then recurse = descending order [OK]

Hint: Print before recursive call prints descending sequence [OK]

Common Mistakes:

• Assuming print happens after recursion
• Including 0 in output
• Confusing order of prints

4. The following recursive method is intended to print numbers from 1 to n. What is the error?

void PrintUp(int n) {
  if (n == 0) return;
  PrintUp(n - 1);
  Console.Write(n + " ");
}

PrintUp(-1);

medium

A. Infinite recursion because negative n never reaches 0

B. No error; it prints numbers correctly

C. Syntax error due to missing return type

D. Runtime error because Console.Write is invalid

Solution

1. Step 1: Analyze base case condition

   Base case stops recursion when n == 0, but if n starts negative, it never reaches 0.

2. Step 2: Effect of negative input

   Calling PrintUp(-1) causes infinite recursion because n keeps decreasing and never hits 0.

3. Final Answer:

   Infinite recursion because negative n never reaches 0 -> Option A

4. Quick Check:

   Base case unreachable with negative input [OK]

Hint: Check base case covers all input ranges [OK]

Common Mistakes:

• Assuming negative input is handled
• Thinking syntax or Console.Write causes error
• Ignoring infinite recursion possibility

5. Consider this recursive method that sums numbers from 1 to n:

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

What is the output of Sum(4) and how many times is the method called?

hard

A. Output: 10, Method calls: 4

B. Output: 10, Method calls: 5

C. Output: 15, Method calls: 5

D. Output: 15, Method calls: 4

Solution

1. Step 1: Calculate Sum(4) step-by-step

   Sum(4) = 4 + Sum(3), Sum(3) = 3 + Sum(2), Sum(2) = 2 + Sum(1), Sum(1) = 1 + Sum(0), Sum(0) = 0. So total = 4+3+2+1+0 = 10.

2. Step 2: Count method calls

   Calls happen for n=4,3,2,1,0 totaling 5 calls.

3. Final Answer:

   Output: 10, Method calls: 5 -> Option B

4. Quick Check:

   Sum 1 to 4 = 10; calls = n+1 [OK]

Hint: Sum calls = n+1; sum formula n(n+1)/2 for output [OK]

Common Mistakes:

• Counting calls as n instead of n+1
• Calculating sum incorrectly
• Ignoring base case call