Recursion Concept and Call Stack Visualization in DSA Java

Mental Model

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

Analogy: Imagine a set of Russian dolls where each doll opens to reveal a smaller doll inside until the smallest doll is reached and then you close them back up in reverse order.

function call -> function call -> function call -> base case reached
↑ current call at top of stack

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down into smaller factorial calls

Step 1: Call factorial(3), which calls factorial(2)

factorial(3) -> factorial(2) ↑

Why: We reduce the problem to a smaller factorial

Step 2: Call factorial(2), which calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Keep breaking down until base case

Step 3: Call factorial(1), which calls factorial(0)

factorial(3) -> factorial(2) -> factorial(1) -> factorial(0) ↑

Why: Reach the base case where factorial(0) = 1

Step 4: Return 1 from factorial(0), then factorial(1) returns 1 x 1 = 1

factorial(3) -> factorial(2) -> factorial(1) ↑ (returning 1)

Why: Start returning values back up the call stack

Step 5: factorial(2) returns 2 x 1 = 2

factorial(3) -> factorial(2) ↑ (returning 2)

Why: Combine returned value with current number

Step 6: factorial(3) returns 3 x 2 = 6

factorial(3) ↑ (returning 6)

Why: Final result computed and returned

Result:

factorial(3) returns 6

Annotated Code

DSA Java

public class RecursionFactorial {
    public static int factorial(int n) {
        if (n == 0) {
            return 1; // base case: factorial(0) = 1
        }
        return n * factorial(n - 1); // recursive call with smaller input
    }

    public static void main(String[] args) {
        int input = 3;
        int result = factorial(input);
        System.out.println("factorial(" + input + ") = " + result);
    }
}

if (n == 0) {

check for base case to stop recursion

return 1; // base case: factorial(0) = 1

return base value to start unwinding calls

return n * factorial(n - 1); // recursive call with smaller input

call factorial with smaller n and multiply result

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) due to the call stack holding n recursive calls at once

vs Alternative: Iterative approach uses O(1) space but recursion is easier to write and understand for factorial

Edge Cases

input is 0

returns 1 immediately as base case

DSA Java

if (n == 0) {

input is 1

calls factorial(0) then returns 1 x 1 = 1

DSA Java

return n * factorial(n - 1);

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a clear stopping point, use recursion to simplify the solution.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops further recursive calls

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call moves closer to the base case

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key is the base case that stops recursion and the call stack that remembers each step.

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