Recursion Concept and Call Stack Visualization in DSA C#

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can answer directly.

Analogy: Imagine a set of Russian nesting dolls where each doll holds a smaller one inside. To open the biggest doll, you first open the smaller one inside, and so on until you reach the smallest doll that can be opened easily.

Function call stack:
main()
 ↑
recursiveFunction(n)
 ↑
recursiveFunction(n-1)
 ↑
...
 ↑
recursiveFunction(base case)
 ↑
returns back up

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursive calls build up and then return results step-by-step

Step 1: Call factorial(3), which calls factorial(2)

Stack: factorial(3) -> factorial(2) ↑

Why: We break the problem into smaller parts by calling factorial with n-1

Step 2: factorial(2) calls factorial(1)

Stack: factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Keep breaking down until we reach the base case

Step 3: factorial(1) calls factorial(0), the base case

Stack: factorial(3) -> factorial(2) -> factorial(1) -> factorial(0) ↑

Why: Base case stops recursion and starts returning values

Step 4: factorial(0) returns 1, factorial(1) returns 1 * 1 = 1

Stack unwinding: factorial(0) returns 1
factorial(1) returns 1

Why: Start returning results back up the call stack

Step 5: factorial(2) returns 2 * 1 = 2

Stack unwinding: factorial(2) returns 2

Why: Combine returned value with current n

Step 6: factorial(3) returns 3 * 2 = 6

Stack unwinding: factorial(3) returns 6

Why: Final result returned to main

Result:

Final result: factorial(3) = 6

Annotated Code

DSA C#

using System;

class RecursionExample
{
    // Recursive function to calculate factorial
    static int Factorial(int n)
    {
        if (n == 0) // base case
            return 1;
        // recursive call with n-1
        return n * Factorial(n - 1);
    }

    static void Main()
    {
        int number = 3;
        int result = Factorial(number);
        Console.WriteLine($"Factorial of {number} is {result}");
    }
}

if (n == 0) // base case

Check if we reached the simplest problem to stop recursion

return 1;

Return 1 for factorial(0) as base case

return n * Factorial(n - 1);

Call factorial with smaller input and multiply by current n

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) because each recursive call adds a new layer to the call stack

vs Alternative: Iterative factorial uses O(1) space but recursion is easier to write and understand for problems naturally defined by smaller subproblems

Edge Cases

Input is 0

Returns 1 immediately as base case

DSA C#

if (n == 0) // base case

Input is 1

Calls factorial(0) then returns 1 * 1 = 1

DSA C#

return n * Factorial(n - 1);

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a clear stopping point, use recursion to simplify the solution.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and stack overflow
Fix: Always include a base case that stops recursion

Mistake: Modifying the input incorrectly in recursive call
Fix: Ensure recursive call moves closer to base case by reducing input properly

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key is the base case that stops recursion and the call stack that holds intermediate results.

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