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 taking one box off at a time until none are left. This is similar to how recursion works in programming, where a function calls itself to solve smaller parts of a problem.

🎯 Goal: You will write a simple recursive function in C to count down from a number to zero, printing each step. This will help you understand how recursion works and how the call stack grows and shrinks.

📋 What You'll Learn

Create a recursive function called countdown that takes an integer parameter n.

The function should print the current value of n.

If n is greater than zero, the function should call itself with n - 1.

Create a variable start with the value 5 to begin the countdown.

Call the countdown function with start.

Print the message "Countdown complete!" after the recursion finishes.

💡 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 important for software developers, especially when working with algorithms, data structures, and problem-solving.

1

Create the countdown function declaration

Write the function declaration for void countdown(int n) in C. Inside the function, add a printf statement to print the current value of n in the format "%d\n".

DSA C

#include 

// Define the countdown function
// Your code here

Hint

Use void countdown(int n) to declare the function. Use printf("%d\n", n); to print the number.

2

Add the recursive call inside countdown

Inside the countdown function, add an if statement that checks if n is greater than zero. If true, call countdown(n - 1) to continue the countdown.

DSA C

#include 

void countdown(int n) {
    printf("%d\n", n);
    // Add recursive call if n > 0
    // Your code here
}

Hint

Use if (n > 0) to check the condition, then call countdown(n - 1); inside the block.

3

Create the start variable and call countdown

In the main function, create an integer variable called start and set it to 5. Then call the countdown function with start as the argument.

DSA C

#include 

void countdown(int n) {
    printf("%d\n", n);
    if (n > 0) {
        countdown(n - 1);
    }
}

int main() {
    // Create start variable and call countdown
    // Your code here
    return 0;
}

Hint

Declare int start = 5; and call countdown(start); inside main.

4

Print completion message after recursion

After calling countdown(start) in main, add a printf statement to print "Countdown complete!\n".

DSA C

#include 

void countdown(int n) {
    printf("%d\n", n);
    if (n > 0) {
        countdown(n - 1);
    }
}

int main() {
    int start = 5;
    countdown(start);
    // Print completion message
    // Your code here
    return 0;
}

Hint

Use printf("Countdown complete!\n"); after the recursive call.

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. The function converts into a loop automatically.

B. It causes infinite recursion and eventually a stack overflow error.

C. The function runs only once and stops.

D. The function returns immediately without doing anything.

Solution

1. Step 1: Understand the role of base case in recursion

   A base case stops the recursion by providing a condition to end the repeated calls.

2. Step 2: Analyze what happens without a base case

   Without a base case, the function keeps calling itself endlessly, filling the call stack until it overflows.

3. Final Answer:

   It causes infinite recursion and eventually a stack overflow error. -> Option B

4. Quick Check:

   No base case = infinite recursion [OK]

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

Common Mistakes:

• Thinking recursion stops automatically without base case
• Confusing recursion with loops
• Assuming function returns without base case

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

easy

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

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

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

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

Solution

1. Step 1: Check base case correctness

   Factorial base case is when n == 0, return 1.

2. Step 2: Check recursive call and operation

   Recursive call should be factorial(n - 1) multiplied by n.

3. Final Answer:

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

4. Quick Check:

   Base case n==0 and multiply with factorial(n-1) [OK]

Hint: Base case returns 1; recursive call uses n-1 [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value or return
• Incorrect recursive call argument

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

void printNumbers(int n) {
  if (n == 0) return;
  printNumbers(n - 1);
  printf("%d ", n);
}

int main() {
  printNumbers(3);
  return 0;
}

medium

A. 1 2 3

B. 3 2 1

C. 0 1 2 3

D. 3 2 1 0

Solution

1. Step 1: Trace recursive calls

   printNumbers(3) calls printNumbers(2), which calls printNumbers(1), then printNumbers(0) returns immediately.

2. Step 2: Print values after recursive calls return

   After reaching base case, prints 1, then 2, then 3 in order.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Print after recursion = ascending order [OK]

Hint: Print after recursive call means ascending order [OK]

Common Mistakes:

• Printing before recursive call (would reverse order)
• Including 0 in output incorrectly
• Confusing base case behavior

4. Identify the error in this recursive function that calculates the sum of numbers from 1 to n:

int sum(int n) {
  if (n == 0) return 0;
  return n + sum(n);
}

medium

A. The recursive call should be sum(n - 1) instead of sum(n).

B. The base case should return n instead of 0.

C. The function should use a loop instead of recursion.

D. The function should return n * sum(n - 1).

Solution

1. Step 1: Analyze recursive call argument

   The function calls sum(n) again without reducing n, causing infinite recursion.

2. Step 2: Correct recursive call to reduce problem size

   It should call sum(n - 1) to move towards base case and stop recursion.

3. Final Answer:

   The recursive call should be sum(n - 1) instead of sum(n). -> Option A

4. Quick Check:

   Recursive call argument must decrease [OK]

Hint: Recursive call must reduce input to reach base case [OK]

Common Mistakes:

• Calling sum(n) again causing infinite recursion
• Changing base case incorrectly
• Using multiplication instead of addition

5. Consider this recursive function to reverse a string:

void reverse(char *str, int start, int end) {
  if (start >= end) return;
  char temp = str[start];
  str[start] = str[end];
  str[end] = temp;
  reverse(str, start + 1, end - 1);
}

int main() {
  char s[] = "hello";
  reverse(s, 0, 4);
  printf("%s", s);
  return 0;
}

What will be printed after running this program?

hard

A. helol

B. hello

C. olleh

D. error

Solution

1. Step 1: Understand the recursive swapping

   The function swaps characters at start and end indexes, then calls itself with start+1 and end-1.

2. Step 2: Trace swaps for "hello"

   Swaps 'h' and 'o' -> "oellh", then swaps 'e' and 'l' -> "olleh", then stops when start >= end.

3. Final Answer:

   olleh -> Option C

4. Quick Check:

   Recursive swaps reverse string [OK]

Hint: Swapping characters inward reverses string recursively [OK]

Common Mistakes:

• Not updating start and end indexes correctly
• Confusing base case condition
• Assuming string prints unchanged