Recursion Concept and Call Stack Visualization in DSA C# - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you have a stack of boxes, and you want to find out how many boxes are in the stack by opening one box at a time and counting. This is similar to how recursion works in programming, where a function calls itself to solve smaller parts of a problem.

🎯 Goal: You will build a simple recursive function in C# that counts down from a number to zero, printing each step. This will help you understand how recursion calls stack up and then unwind.

📋 What You'll Learn

Create a recursive function that prints numbers from a given start down to zero

Use a base case to stop the recursion

Print each number as the function counts down

Understand how the call stack grows and shrinks with recursion

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing tree structures.

💼 Career

Understanding recursion is essential for software developers to solve problems that involve repeated tasks or nested data.

1

Create the Main Method and Starting Number

Create a class Program with a Main method. Inside Main, create an integer variable called startNumber and set it to 5.

DSA C#

class Program
{
    static void Main(string[] args)
    {
        // Create an integer variable called startNumber and set it to 5
        // Your code here
    }
}

Hint

Remember to define the class and the Main method exactly as shown. Then create the variable startNumber with the value 5.

2

Add the Recursive Method Signature

Inside the Program class but outside Main, create a static method called CountDown that takes an integer parameter named number.

DSA C#

class Program
{
    static void Main(string[] args)
    {
        int startNumber = 5;
    }

    // Create a static method called CountDown with an int parameter named number
    // Your code here
}

Hint

Define the method CountDown as static so it can be called from Main. It should accept one integer parameter named number.

3

Implement the Recursive Logic with Base Case

Inside the CountDown method, write an if statement that checks if number is less than 0. If yes, return to stop recursion. Otherwise, print number and call CountDown again with number - 1. Also, call CountDown from Main with startNumber.

DSA C#

class Program
{
    static void Main(string[] args)
    {
        int startNumber = 5;
        // Call CountDown with startNumber
        // Your code here
    }

    static void CountDown(int number)
    {
        // If number is less than 0, return
        // Otherwise, print number and call CountDown with number - 1
        // Your code here
    }
}

Hint

The base case stops recursion when number is less than 0. Otherwise, print the number and call CountDown with one less.

4

Run and Observe the Output

Run the program and observe the output printed to the console. It should print numbers from 5 down to 0, each on its own line.

DSA C#

using System;

class Program
{
    static void Main(string[] args)
    {
        int startNumber = 5;
        CountDown(startNumber);
    }

    static void CountDown(int number)
    {
        if (number < 0)
        {
            return;
        }
        Console.WriteLine(number);
        CountDown(number - 1);
    }
}

// Run the program to see the output

Hint

The program should print numbers starting from 5 down to 0, each on a new line.

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