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

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you are helping a friend understand how recursion works by using a simple example: calculating the factorial of a number. Factorial means multiplying a number by all the numbers below it down to 1. For example, 4 factorial (written as 4!) is 4 x 3 x 2 x 1 = 24.We will write a Java program that uses recursion to find the factorial of a number and also prints messages to show how the program calls itself and returns results step by step.

🎯 Goal: Build a Java program that calculates the factorial of a number using recursion. The program will also print messages to show when the function is called and when it returns a value, helping you visualize the call stack and understand recursion better.

📋 What You'll Learn

Create a method called factorial that takes an integer n and returns the factorial of n using recursion.

Add print statements inside the factorial method to show when the method is called and what value it returns.

Call the factorial method from the main method with the number 5.

Print the final factorial result in the main method.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like navigating file systems, solving puzzles, and processing hierarchical data.

💼 Career

Understanding recursion and call stacks is essential for software developers, especially when working with algorithms, debugging, and optimizing code.

1

Create the main class and main method

Create a public class called FactorialDemo with a main method. Inside the main method, declare an integer variable number and set it to 5.

DSA Java

public class FactorialDemo {
    public static void main(String[] args) {
        // Your code here
    }
}

Hint

Start by writing the class and main method structure. Then create the variable number and assign it the value 5.

2

Add the recursive factorial method

Add a public static method called factorial that takes an integer parameter n and returns an integer. Inside the method, write the base case: if n is 1, return 1. Otherwise, return n * factorial(n - 1).

DSA Java

public class FactorialDemo {
    public static void main(String[] args) {
        int number = 5;
    }

    // Your code here
}

Hint

Remember the base case stops the recursion. For other cases, call factorial again with n - 1 and multiply the result by n.

3

Add print statements to visualize recursion calls

Inside the factorial method, add a print statement at the start to show "Calling factorial with n = " followed by n. Before returning the result, add another print statement to show "Returning from factorial with n = " followed by n and the result value.

DSA Java

public class FactorialDemo {
    public static void main(String[] args) {
        int number = 5;
    }

    public static int factorial(int n) {
        // Your code here
    }
}

Hint

Print the message before the base case check and also before returning the result in the recursive case.

4

Call factorial and print the final result

In the main method, call the factorial method with the variable number and store the result in an integer variable called fact. Then print "Factorial of 5 is: " followed by fact.

DSA Java

public class FactorialDemo {
    public static void main(String[] args) {
        int number = 5;
        // Your code here
    }

    public static int factorial(int n) {
        System.out.println("Calling factorial with n = " + n);
        if (n == 1) {
            System.out.println("Returning from factorial with n = 1 and result = 1");
            return 1;
        } else {
            int result = n * factorial(n - 1);
            System.out.println("Returning from factorial with n = " + n + " and result = " + result);
            return result;
        }
    }
}

Hint

Call the factorial method with number, save the result in fact, and print the final message.

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