Recursion Concept and Call Stack Visualization in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in programming?

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

beginner

What is a base case in recursion?

A base case is the simplest situation in a recursive function that stops the recursion by not calling itself again.

intermediate

How does the call stack help in recursion?

The call stack keeps track of all the active function calls. Each recursive call adds a new layer, and when a base case is reached, the stack unwinds as functions return their results.

intermediate

What happens if a recursive function has no base case?

Without a base case, the recursive function keeps calling itself forever, causing a stack overflow error because the call stack grows too large.

beginner

Explain the flow of a simple factorial function using recursion.

The factorial function calls itself with smaller numbers until it reaches 1 (base case). Then it returns 1, and each previous call multiplies its number by the returned value, building the final result.

What is the purpose of the base case in a recursive function?

A To increase the size of the problem

B To call the function again with the same input

C To stop the recursion and prevent infinite calls

D To print the result

The base case stops the recursion by providing a simple answer without further calls.

What does the call stack do during recursion?

A Runs functions in parallel

B Deletes previous function calls immediately

C Prevents recursion from happening

D Stores all active function calls until they finish

The call stack keeps track of each recursive call until the base case is reached and functions return.

What error occurs if a recursive function never reaches a base case?

A Stack overflow

B Syntax error

C Type error

D Memory leak

Without a base case, the call stack grows until it runs out of space, causing a stack overflow.

In the factorial example, what does factorial(3) call next?

A factorial(2)

B factorial(4)

C factorial(1)

D factorial(0)

factorial(3) calls factorial(2) to solve a smaller problem.

Which of these is NOT true about recursion?

A Every recursive function must have a base case

B Recursion always uses loops internally

C Recursion breaks a problem into smaller parts

D The call stack grows with each recursive call

Recursion does not require loops; it uses function calls to repeat.

Describe how the call stack changes during a recursive function call.

Think about how each call waits for the next before finishing.

Explain why a base case is essential in recursion and what happens if it is missing.

Consider what stops the function from calling itself forever.

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