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 where the answer is known and the function stops calling itself.

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 to the stack until the base case is reached, then the stack unwinds.

intermediate

What happens if a recursive function has no base case?

Without a base case, the 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 multiplies the numbers as the call stack unwinds, giving the final result.

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

A To increase the call stack size

B To call the function again

C To stop the recursion and return a result

D To create an infinite loop

The base case stops the recursion by providing a simple answer, preventing infinite calls.

What does the call stack do during recursion?

A Stores active function calls in order

B Deletes previous function calls immediately

C Runs functions in parallel

D Prevents recursion from happening

The call stack keeps track of each function call until the base case is reached.

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 overflows, causing a stack overflow error.

In the factorial example, what is the base case?

A factorial(0) = 0

B factorial(1) = 1

C factorial(n) = n * factorial(n-1)

D factorial(n) = n + 1

The base case for factorial is when n equals 1, returning 1 directly.

Which of these is a sign of a recursive function?

A Function returns a constant value always

B Function uses loops only

C Function never calls another function

D Function calls itself

A recursive function calls itself to solve smaller parts of the problem.

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

Think about how the computer remembers each call until it finishes.

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 keeps calling itself indefinitely, causing a stack overflow

B. The function stops immediately without any output

C. The function returns zero by default

D. The function executes only once and then stops

Solution

1. Step 1: Understand recursion base case role

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

2. Step 2: Analyze missing base case effect

   Without a base case, the function calls itself endlessly, filling the call stack.

3. Final Answer:

   The function keeps calling itself indefinitely, causing a stack overflow -> Option A

4. Quick Check:

   No base case = infinite calls [OK]

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

Common Mistakes:

• Thinking recursion stops automatically
• Assuming default return value ends recursion
• Confusing base case with recursive step

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) { while (n > 0) return n * factorial(n - 1); }

B. int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 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

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } uses base case n == 0 returning 1, which is correct for factorial.

2. Step 2: Verify recursive call and operation

   int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } multiplies n by factorial(n-1), matching factorial definition.

3. Final Answer:

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

4. Quick Check:

   Correct base case and recursive step = int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Base case returns 1 for factorial of 0 [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value
• 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);
  std::cout << n << " ";
}

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

medium

A. 3 2 1

B. 3 2 1 0

C. 1 2 3

D. 1 2 3 0

Solution

1. Step 1: Trace recursive calls

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

2. Step 2: Print values after returning from recursion

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

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Print after recursion = ascending order [OK]

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

Common Mistakes:

• Printing before recursive call (would reverse order)
• Including zero in output
• Confusing call stack order

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

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

medium

A. The base case is incorrect; it should be n == 0

B. The function should return n * sum(n - 1) instead of addition

C. The function lacks a return statement in the base case

D. The recursive call uses the same argument n, causing infinite recursion

Solution

1. Step 1: Check recursive call argument

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

2. Step 2: Identify fix for recursion

   The recursive call should be sum(n - 1) to reduce n and reach base case.

3. Final Answer:

   The recursive call uses the same argument n, causing infinite recursion -> Option D

4. Quick Check:

   Recursive call argument must decrease [OK]

Hint: Recursive calls must progress toward base case [OK]

Common Mistakes:

• Not decreasing argument in recursion
• Wrong base case value
• Confusing addition with multiplication

5. Consider this recursive function to compute the nth Fibonacci number:

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

What is the number of times fib(1) is called when fib(4) is executed?

hard

A. 3

B. 2

C. 5

D. 4

Solution

1. Step 1: Expand fib(4) calls

   fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0).

2. Step 2: Count fib(1) calls

   fib(1) is called once from fib(3), once from fib(2) inside fib(3), and once from fib(2) directly called by fib(4). Total 3 times.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count base calls in recursion tree = 3 [OK]

Hint: Draw recursion tree to count base calls [OK]

Common Mistakes:

• Counting calls only once per function
• Ignoring repeated calls in recursion
• Confusing fib(1) with fib(0)