Recursion Concept and Call Stack Visualization in DSA Javascript - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you have a stack of boxes, and you want to count how many boxes are in the stack by opening one box at a time from the top until there are no more boxes left.This project will help you understand how recursion works by simulating this counting process step-by-step.

🎯 Goal: You will write a recursive function called countBoxes that counts the number of boxes in a stack represented by a number. You will also visualize the call stack by printing messages when the function is called and when it returns.

📋 What You'll Learn

Create a variable called totalBoxes with the value 5 representing the number of boxes in the stack.

Create a variable called callCount initialized to 0 to count how many times the recursive function is called.

Write a recursive function called countBoxes that takes a number n and returns the count of boxes.

Inside countBoxes, print a message when the function is called and when it returns to visualize the call stack.

Call countBoxes with totalBoxes and print the final count.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing nested data.

💼 Career

Understanding recursion helps in software development roles that involve algorithms, data processing, and problem-solving.

1

Create the initial data setup

Create a variable called totalBoxes and set it to 5 representing the number of boxes in the stack.

DSA Javascript

// Create a variable called totalBoxes and set it to 5
// Your code here

Hint

Use const totalBoxes = 5; to create the variable.

2

Add a counter for recursive calls

Create a variable called callCount and set it to 0 to count how many times the recursive function is called.

DSA Javascript

const totalBoxes = 5;
// Create a variable called callCount and set it to 0
// Your code here

Hint

Use let callCount = 0; to create the counter variable.

3

Write the recursive function

Write a recursive function called countBoxes that takes a parameter n. Inside the function, increase callCount by 1, print "Calling countBoxes with n = " plus the value of n. If n is 0, return 0. Otherwise, return 1 plus the result of calling countBoxes with n - 1. Before returning, print "Returning from countBoxes with n = " plus the value of n.

DSA Javascript

const totalBoxes = 5;
let callCount = 0;
// Write the recursive function countBoxes as described
// Your code here

Hint

Remember to increase callCount and print messages before and after the recursive call.

4

Call the function and print the result

Call the function countBoxes with totalBoxes and store the result in a variable called finalCount. Then print "Total boxes counted: " plus finalCount. Also print "Total recursive calls: " plus callCount.

DSA Javascript

const totalBoxes = 5;
let callCount = 0;

function countBoxes(n) {
    callCount++;
    console.log("Calling countBoxes with n = " + n);
    if (n === 0) {
        console.log("Returning from countBoxes with n = " + n);
        return 0;
    } else {
        const result = 1 + countBoxes(n - 1);
        console.log("Returning from countBoxes with n = " + n);
        return result;
    }
}

// Call countBoxes with totalBoxes and print the final count and callCount
// Your code here

Hint

Call countBoxes(totalBoxes), save the result, and print the messages as described.

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