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

Concept Flow - Recursion Concept and Call Stack Visualization

Call function with input

↓

Check base case?

↓

Return value

↓

Wait for returned value

↓

Process returned value

↓

Return result

Recursion calls itself with smaller inputs until a base case stops the calls, then returns values back up the call stack.

Execution Sample

DSA Javascript

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(3));

Calculates factorial of 3 by calling itself with smaller numbers until 0, then multiplies back up.

Execution Table

Step	Operation	Input n	Call Stack Depth	Return Value	Call Stack Visual
1	Call factorial(3)	3	1	?	factorial(3)
2	Call factorial(2)	2	2	?	factorial(3) -> factorial(2)
3	Call factorial(1)	1	3	?	factorial(3) -> factorial(2) -> factorial(1)
4	Call factorial(0)	0	4	?	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
5	Base case reached, return 1	0	4	1	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
6	Return from factorial(0), compute 1 * 1	1	3	1	factorial(3) -> factorial(2) -> factorial(1)
7	Return from factorial(1), compute 2 * 1	2	2	2	factorial(3) -> factorial(2)
8	Return from factorial(2), compute 3 * 2	3	1	6	factorial(3)
9	Return from factorial(3), final result 6	3	0	6

💡 Recursion ends when base case n=0 is reached and all calls return their computed values back up.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
n	-	3	2	1	0	0	1	2	3	-
Call Stack Depth	0	1	2	3	4	4	3	2	1	0
Return Value	-	?	?	?	?	1	1	2	6	6
Call Stack Visual	-	factorial(3)	factorial(3) -> factorial(2)	factorial(3) -> factorial(2) -> factorial(1)	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	factorial(3) -> factorial(2) -> factorial(1)	factorial(3) -> factorial(2)	factorial(3)

Key Moments - 3 Insights

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

Because the base case (n === 0) is not met yet, so the function calls itself with smaller input (n-1) as shown in steps 1 to 4 in the execution_table.

When does the function start returning values instead of calling itself?

At step 5, when the base case n=0 is reached, the function returns 1 and then starts returning back up the call stack as seen in steps 6 to 9.

What does the call stack visual show in the execution_table?

It shows the chain of active function calls waiting for results. The stack grows with each recursive call (steps 1-4) and shrinks as calls return (steps 5-9).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the call stack depth?

A 1

B 3

C 4

D 0

💡 Hint

Check the 'Call Stack Depth' column at step 4 in the execution_table.

At which step does the function reach the base case and return 1?

A Step 3

B Step 5

C Step 7

D Step 9

💡 Hint

Look for the step where 'Base case reached' and return value is 1 in the execution_table.

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

A It would be 5

B It would be 3

C It would be 4

D It would be 2

💡 Hint

Each recursive call adds 1 to the call stack depth; factorial(4) adds one more call than factorial(3).

Concept Snapshot

Recursion calls a function inside itself with smaller input.
Base case stops recursion and returns a value.
Calls build up on the call stack.
Returns happen from base case back up.
Call stack depth shows active calls.
Visualize recursion as stacking and unstacking calls.

Full Transcript

Recursion is when a function calls itself with smaller inputs until it reaches a base case. The base case stops further calls and returns a value. Each call waits for the next call to finish, creating a stack of calls called the call stack. When the base case returns, the calls return their results back up the stack. This process can be visualized step-by-step by tracking the input, call stack depth, and return values. The call stack grows as calls happen and shrinks as they return. Understanding this helps see how recursion works internally.

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. It returns immediately without doing anything

B. It causes an infinite loop leading to a stack overflow error

C. It executes only once and stops

D. It throws a syntax error

Solution

1. Step 1: Understand the role of base case in recursion

   The base case stops the recursion by providing a condition to end 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.

3. Final Answer:

   It causes an infinite loop leading to a stack overflow error -> Option B

4. Quick Check:

   No base case = infinite recursion = stack overflow [OK]

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

Common Mistakes:

• Thinking recursion stops automatically
• Confusing base case with recursive case
• Assuming syntax error occurs without base case

2. Which of the following is the correct syntax to define a recursive function countDown in JavaScript?

easy

A. function countDown(n) { if(n <= 0) return; countDown(n - 1); }

B. function countDown(n) { while(n > 0) countDown(n - 1); }

C. function countDown(n) { for(let i=0; i

D. function countDown(n) { if(n < 0) countDown(n + 1); }

Solution

1. Step 1: Identify correct base case and recursive call

   function countDown(n) { if(n <= 0) return; countDown(n - 1); } has a base case (if n <= 0 return) and calls itself with n-1.

2. Step 2: Check other options for syntax or logic errors

   function countDown(n) { while(n > 0) countDown(n - 1); } uses while loop causing infinite recursion; C uses for loop incorrectly; D lacks proper base case.

3. Final Answer:

   function countDown(n) { if(n <= 0) return; countDown(n - 1); } -> Option A

4. Quick Check:

   Base case + recursive call = correct syntax [OK]

Hint: Look for base case and self-call in function [OK]

Common Mistakes:

• Using loops instead of recursion
• Missing base case
• Wrong recursive call argument

3. What is the output of the following code?

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(3));

medium

A. 9

B. 1

C. 3

D. 6

Solution

1. Step 1: Trace factorial calls for n=3

   factorial(3) = 3 * factorial(2); factorial(2) = 2 * factorial(1); factorial(1) = 1 * factorial(0); factorial(0) = 1.

2. Step 2: Calculate return values step-by-step

   factorial(1) = 1 * 1 = 1; factorial(2) = 2 * 1 = 2; factorial(3) = 3 * 2 = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   3! = 6 [OK]

Hint: Factorial n! = n * (n-1)! [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting base case returns 1
• Calculating factorial(0) incorrectly

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

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

medium

A. The base case is missing

B. The function should return n - sum(n - 1)

C. The recursive call uses the same argument causing infinite recursion

D. The function should use a loop instead

Solution

1. Step 1: Check the recursive call argument

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

2. Step 2: Identify correct recursive call

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

3. Final Answer:

   The recursive call uses the same argument causing infinite recursion -> Option C

4. Quick Check:

   Recursive call argument must change to reach base case [OK]

Hint: Recursive call argument must move toward base case [OK]

Common Mistakes:

• Calling function with same argument
• Missing base case
• Using wrong operator in return

5. Consider this recursive function that reverses a string:

function reverseStr(str) {
  if (str === "") return "";
  return reverseStr(str.substring(1)) + str[0];
}
console.log(reverseStr("code"));

What is the output and why?

hard

A. "edoc" because the function moves first character to the end recursively

B. "code" because substring does not change the string

C. "" because base case returns empty string immediately

D. SyntaxError because substring is used incorrectly

Solution

1. Step 1: Understand recursion on string substring

   The function calls itself with the string minus the first character each time.

2. Step 2: Trace the concatenation on return

   Each call adds the first character of the current string to the end of the reversed substring, reversing the string.

3. Final Answer:

   "edoc" because the function moves first character to the end recursively -> Option A

4. Quick Check:

   Recursive substring + concat reverses string [OK]

Hint: Recursion with substring(1) + first char reverses string [OK]

Common Mistakes:

• Thinking substring does not change string
• Confusing base case effect
• Assuming syntax error with substring