Recursion Concept and Call Stack Visualization in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Simple Recursive Sum

What is the output of the following Java code that uses recursion to sum numbers from 1 to n?

DSA Java

public class Main {
    public static int sum(int n) {
        if (n == 0) return 0;
        return n + sum(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(sum(4));
    }
}

A 10

B 24

C 0

D StackOverflowError

💡 Hint

Think about how the function adds numbers from n down to 0.

The function sums 4 + 3 + 2 + 1 + 0 = 10. It stops when n reaches 0.

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What will be printed when the following Java program runs?

DSA Java

public class Main {
    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}

A 1

B 24

C 5

D 120

💡 Hint

Factorial multiplies all numbers from n down to 1.

5! = 5 * 4 * 3 * 2 * 1 = 120.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci

The following Java code tries to print the 6th Fibonacci number using recursion. What error will it cause?

DSA Java

public class Main {
    public static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }
    public static void main(String[] args) {
        System.out.println(fib(6));
    }
}

A Prints 5

B It prints 8

C Compilation error

D StackOverflowError

💡 Hint

Trace the calls for fib(6) carefully.

fib(6) = fib(5) + fib(4) = 5 + 3 = 8. No error occurs.

❓ Predict Output

advanced

Output of Recursive String Reverse

What is the output of this Java program that reverses a string recursively?

DSA Java

public class Main {
    public static String reverse(String s) {
        if (s.isEmpty()) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }
    public static void main(String[] args) {
        System.out.println(reverse("code"));
    }
}

A edocedoc

B code

C edoc

D StackOverflowError

💡 Hint

Each recursive call removes the first character and adds it at the end.

The function reverses the string by moving first character to the end recursively.

🧠 Conceptual

expert

Maximum Call Stack Depth in Recursive Calls

Consider this recursive Java method that counts down from n to 0. What is the maximum number of active calls on the call stack when calling countdown(5)?

DSA Java

public class Main {
    public static void countdown(int n) {
        if (n < 0) return;
        countdown(n - 1);
    }
    public static void main(String[] args) {
        countdown(5);
    }
}

A 6

B 5

C 7

D StackOverflowError

💡 Hint

Count how many calls happen before the base case stops recursion.

Calls happen for n=5,4,3,2,1,0 before stopping at n=-1. So 6 calls active at peak.

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