Recursion Concept and Call Stack Visualization in DSA Java - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Start Recursive Function Call

↓

Check Base Case?

Yes→Return Base Value

No↓

Make Recursive Call with Smaller Input

↓

Wait for Recursive Call Result

↓

Process Result and Return

↓

End Current Call

↓

Return to Previous Call or Main

Shows how a recursive function calls itself until a base case is met, then returns values back up the call stack.

Execution Sample

DSA Java

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

System.out.println(factorial(3));

Calculates factorial of 3 using recursion, multiplying n by factorial of n-1 until base case 0.

Execution Table

Step	Operation	Current n	Call Stack (Top to Bottom)	Return Value	Visual Call Stack
1	Call factorial(3)	3	factorial(3)		factorial(3)
2	Check if n==0	3	factorial(3)	No	factorial(3)
3	Call factorial(2)	2	factorial(2) -> factorial(3)		factorial(2) ↑ factorial(3)
4	Check if n==0	2	factorial(2) -> factorial(3)	No	factorial(2) ↑ factorial(3)
5	Call factorial(1)	1	factorial(1) -> factorial(2) -> factorial(3)		factorial(1) ↑ factorial(2) ↑ factorial(3)
6	Check if n==0	1	factorial(1) -> factorial(2) -> factorial(3)	No	factorial(1) ↑ factorial(2) ↑ factorial(3)
7	Call factorial(0)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)		factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
8	Check if n==0	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	Yes	factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
9	Return 1 (base case)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	1	factorial(0) returns 1 ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
10	Calculate 1 * 1	1	factorial(1) -> factorial(2) -> factorial(3)		factorial(1) computes 1 * factorial(0)
11	Return 1	1	factorial(1) -> factorial(2) -> factorial(3)	1	factorial(1) returns 1 ↑ factorial(2) ↑ factorial(3)
12	Calculate 2 * 1	2	factorial(2) -> factorial(3)		factorial(2) computes 2 * factorial(1)
13	Return 2	2	factorial(2) -> factorial(3)	2	factorial(2) returns 2 ↑ factorial(3)
14	Calculate 3 * 2	3	factorial(3)		factorial(3) computes 3 * factorial(2)
15	Return 6	3	factorial(3)	6	factorial(3) returns 6
16	Print result			6	Call stack empty, result 6 printed

💡 All recursive calls returned; factorial(3) computed as 6 and printed.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	After Step 15	Final
n		3	2	1	0	1	1	2	3
Return Value						1	1	2	6	6
Call Stack Depth	0	1	2	3	4	3	2	1	0	0

Key Moments - 3 Insights

Why does the function keep calling itself instead of returning immediately?

Because the base case (n == 0) is not met yet, the function calls itself with smaller n (see steps 1-7 in execution_table). It waits for the deeper call to return before continuing.

How does the function know when to stop calling itself?

When n reaches 0, the base case returns 1 immediately (step 8-9). This stops further recursive calls and starts returning values back up the call stack.

What does the call stack look like during recursion?

The call stack grows with each recursive call (steps 3,5,7) and shrinks as calls return (steps 9,11,13,15). The Visual Call Stack column shows this clearly.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the current call stack?

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

B factorial(3) only

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

D factorial(2) -> factorial(3)

💡 Hint

Check the 'Call Stack (Top to Bottom)' column at step 7 in execution_table.

At which step does the base case return its value?

A Step 6

B Step 12

C Step 9

D Step 15

💡 Hint

Look for 'Return 1 (base case)' in the 'Operation' column of execution_table.

If the initial call was factorial(4) instead of factorial(3), how would the call stack depth change at step 7?

A It would remain 4

B It would be 5 instead of 4

C It would be 3

D It would be 6

💡 Hint

Check 'Call Stack Depth' in variable_tracker and consider one more recursive call.

Concept Snapshot

Recursion calls a function within itself.
Each call waits for the next until base case.
Base case stops recursion and returns value.
Call stack grows with calls, shrinks with returns.
Use base case to avoid infinite recursion.
Visualize call stack to understand flow.

Full Transcript

Recursion is when a function calls itself with smaller inputs until a base case is reached. The base case returns a value immediately, stopping further calls. Each recursive call waits for the next call's result before continuing. This creates a call stack that grows with each call and shrinks as calls return. For example, factorial(3) calls factorial(2), factorial(1), factorial(0). When factorial(0) returns 1, the calls return back multiplying results until factorial(3) returns 6. Visualizing the call stack helps understand how recursion works step-by-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