Recursion Concept and Call Stack Visualization in DSA Java - 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 the base case in a recursive function?

The base case is the simplest situation where the function stops calling itself and returns a result directly.

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 returning results step by step.

beginner

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.

intermediate

Explain the flow of a simple factorial recursive function call for factorial(3).

factorial(3) calls factorial(2), which calls factorial(1). factorial(1) returns 1 (base case). Then factorial(2) returns 2 * 1 = 2, and factorial(3) returns 3 * 2 = 6.

What is the purpose of the base case in recursion?

A To cause an error

B To call the function again

C To increase the call stack size

D To stop the recursion and return a result

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

What does the call stack do during recursion?

A Runs functions in parallel

B Deletes previous calls immediately

C Keeps track of active function calls

D Prevents recursion

The call stack stores each function call until it finishes, helping manage recursive calls.

What error occurs if recursion has no base case?

A Stack overflow

B Syntax error

C Null pointer exception

D Divide by zero

Without a base case, recursion never ends, causing the call stack to overflow.

In factorial(3), how many times does the function call itself?

A 2 times

B 3 times

C 1 time

D 4 times

factorial(3) calls factorial(2), which calls factorial(1). So it calls itself 2 times.

Which of these is a correct base case for factorial(n)?

A if n > 0 return n

B if n == 0 return 1

C if n == 1 return 0

D if n < 0 return n

The factorial of 0 is 1, so returning 1 when n == 0 is the correct base case.

Describe how recursion works using the example of calculating factorial of a number.

Think about how factorial(n) calls factorial(n-1) until it reaches 0.

Explain the role of the call stack in managing recursive function calls.

Imagine stacking plates and removing them one by one.

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It converts into a loop automatically.

B. It runs only once and stops automatically.

C. It causes infinite recursion leading to a stack overflow error.

D. It returns null immediately.

Solution

1. Step 1: Understand recursion without base case

   A recursive function without a stopping condition keeps calling itself endlessly.

2. Step 2: Effect on call stack

   Each call adds a new frame to the call stack until memory runs out, causing a stack overflow error.

3. Final Answer:

   It causes infinite recursion leading to a stack overflow error. -> Option C

4. Quick Check:

   Missing base case = stack overflow [OK]

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

Common Mistakes:

• Assuming recursion stops automatically
• Thinking recursion converts to loop
• Believing it returns null without base case

2. Which of the following is the correct syntax to define a recursive method in Java?

easy

A. public void recurse() { recurse(); }

B. public void recurse() { return recurse(); }

C. public void recurse() { if(true recurse(); }

D. public void recurse() { recurse; }

Solution

1. Step 1: Check method call syntax

   public void recurse() { recurse(); } correctly calls the method recurse() inside itself using parentheses.

2. Step 2: Identify syntax errors in other options

   public void recurse() { return recurse(); } tries to return void method call, invalid. public void recurse() { if(true recurse(); } missing parenthesis after if condition, invalid syntax. public void recurse() { recurse; } misses parentheses, invalid call.

3. Final Answer:

   public void recurse() { recurse(); } -> Option A

4. Quick Check:

   Method call needs parentheses [OK]

Hint: Recursive calls must use parentheses like normal method calls [OK]

Common Mistakes:

• Omitting parentheses in recursive call
• Returning void method call
• Using invalid syntax inside method

3. What will be the output of the following Java code?

public class Test {
  public static void printNumbers(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    printNumbers(n - 1);
  }
  public static void main(String[] args) {
    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 recursive calls and prints

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

2. Step 2: Output order

   Numbers print before recursive call, so output is "3 2 1 " with no zero printed.

3. Final Answer:

   3 2 1 -> Option D

4. Quick Check:

   Print before recursion = descending order [OK]

Hint: Print before recursion call prints descending sequence [OK]

Common Mistakes:

• Expecting ascending order output
• Including zero in output
• Confusing print order with recursion

4. Identify the error in the following recursive Java method and select the fix:

public static int factorial(int n) {
  if (n == 1) return 1;
  else return n * factorial(n);
}

medium

A. Add print statement before recursive call

B. Change recursive call to factorial(n - 1)

C. Change base case to if (n == 0) return 0

D. Change return type to void

Solution

1. Step 1: Analyze recursive call parameter

   The method calls factorial(n) again without reducing n, causing infinite recursion.

2. Step 2: Correct recursive call

   It should call factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Change recursive call to factorial(n - 1) -> Option B

4. Quick Check:

   Recursive call must reduce parameter [OK]

Hint: Recursive calls must move toward base case by changing parameters [OK]

Common Mistakes:

• Calling factorial with same argument causing infinite recursion
• Wrong base case value
• Changing return type unnecessarily

5. Consider the following recursive method to compute the sum of digits of a positive integer:

public static int sumDigits(int n) {
  if (n == 0) return 0;
  return (n % 10) + sumDigits(n / 10);
}

What is the output of sumDigits(1234) and explain how the call stack evolves?

hard

A. 10; Calls: sumDigits(1234) -> sumDigits(123) -> sumDigits(12) -> sumDigits(1) -> sumDigits(0)

B. 1234; Calls: sumDigits(1234) only once

C. 0; Calls: sumDigits(0) only

D. 15; Calls: sumDigits(1234) -> sumDigits(123) -> sumDigits(12) -> sumDigits(1) -> sumDigits(0)

Solution

1. Step 1: Trace recursive calls and sums

   sumDigits(1234) = 4 + sumDigits(123), sumDigits(123) = 3 + sumDigits(12), sumDigits(12) = 2 + sumDigits(1), sumDigits(1) = 1 + sumDigits(0), sumDigits(0) = 0.

2. Step 2: Calculate total sum and call stack order

   Total sum = 4+3+2+1+0 = 10. The call stack grows with calls: 1234 -> 123 -> 12 -> 1 -> 0, then unwinds adding digits.

3. Final Answer:

   10; Calls: sumDigits(1234) -> sumDigits(123) -> sumDigits(12) -> sumDigits(1) -> sumDigits(0) -> Option A

4. Quick Check:

   Sum digits = 10, call stack grows with decreasing n [OK]

Hint: Sum digits by adding last digit and recurse on rest [OK]

Common Mistakes:

• Adding digits incorrectly
• Misunderstanding call stack order
• Confusing sum with original number