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

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

int main() {
    int result = factorial(4);
    printf("%d", result);
    return 0;
}

A 24

B 10

C 120

D 0

💡 Hint

Recall that factorial of n is n multiplied by factorial of n-1, with factorial(0) = 1.

The factorial function multiplies numbers from n down to 1 recursively. factorial(4) = 4 * 3 * 2 * 1 = 24.

❓ Predict Output

intermediate

Output of Recursive Sum Function

What will be printed after executing this C code snippet?

DSA C

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

int main() {
    printf("%d", sum(5));
    return 0;
}

A 10

B 15

C 5

D 0

💡 Hint

Sum of first n natural numbers is n*(n+1)/2.

The function adds numbers from 5 down to 1 recursively: 5+4+3+2+1=15.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Function

What error will occur when running this C code?

DSA C

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int result = fibonacci(-1);
    printf("%d", result);
    return 0;
}

A Compilation error

B Prints 0

C Stack overflow due to infinite recursion

D Prints 1

💡 Hint

Consider what happens when n is negative in the recursive calls.

The function does not handle negative input, so calls fibonacci(-1), fibonacci(-2), etc., causing infinite recursion and stack overflow.

🧠 Conceptual

advanced

Call Stack Depth in Recursive Function

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

A 1

B 7

C 6

D 8

💡 Hint

Count the initial call plus all recursive calls until base case.

The call stack includes the initial call plus one call for each decrement until 0, so total 8 calls.

🚀 Application

expert

Output of Recursive String Reverse Function

What is the output of this C program that reverses a string recursively?

DSA C

#include <stdio.h>
#include <string.h>

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, strlen(s) - 1);
    printf("%s", s);
    return 0;
}

A olleh

B hello

C ohlle

D error

💡 Hint

The function swaps characters from start and end moving inward.

The function swaps first and last characters recursively until the middle is reached, reversing the string.

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