<?xml version="1.0" encoding="UTF-8"?>

<chapter xml:id="recursion-in-java">

<title>Recursion in Java</title>

<introduction>

</introduction>

<section xml:id="basic-recursion">

<title>Basic Recursion</title>

<p>

In this chapter, we will explore how to translate your recursive logic from Python to Java. While the core concepts of recursion remain the same, the syntax and structure of your code will change somewhat.

</p>

<p><idx>recursion</idx>

As you may know from Python, <term>recursion</term> is a powerful problem-solving technique involving base cases and recursive steps in which a function or method calls itself. When moving to Java, the core logic you've learned remains identical. The challenge is adapting that logic to Java's statically-typed, class-based syntax.

</p>

<p>

Let's take the familiar factorial function (which calculates the factorial of a number, namely the product of all positive integers from 1 to n). The logical steps in the code are the same, but the implementation details change.

</p>

<p>

Here is the standard implementation in Python:

</p>

<program interactive="activecode" language="python">

<code>

class MathTools:

"""A utility class for mathematical operations."""

def factorial(n: int) -&gt; int:

"""Calculates the factorial of n using recursion."""

# A check for negative numbers is good practice.

if n &lt; 0:

raise ValueError("Factorial is not defined for negative numbers.") # Base Case: 0! or 1! is 1

if n &lt;= 1:

return 1 # Recursive Step: n * (n-1)!

# The call is now to the method within the class.

return n * MathTools.factorial(n - 1)# This block shows how to use the class method.

if __name__ == "__main__":

number = 5

result = MathTools.factorial(number) # Call the method on the class

print(f"{number}! is {result}")

</code>

</program>

<p>

The Java version follows the same recursive logic but requires three key syntax changes: the method must be inside a class, you must declare the parameter and return types (<c>int n</c> and <c>int return</c>), and you use <c>public static</c> to make it callable from <c>main</c>. The base case and recursive step remain conceptually identical.

</p>

<p>

Here is the equivalent Java code:

</p>

<program interactive="activecode" language="java">

<code>

public class MathTools { /**

* Calculates the factorial of n using recursion.

* This is a static method, like Python's @staticmethod.

* @param n The non-negative integer.

* @return The factorial of n as a long to prevent overflow for larger numbers.

*/

public static int factorial(int n) {

// A check for negative numbers is good practice.

if (n &lt; 0) {

throw new IllegalArgumentException("Factorial is not defined for negative numbers.");

} // Base Case: 0! or 1! is 1

if (n &lt;= 1) {

return 1;

} // Recursive Step: n * (n-1)!

return n * factorial(n - 1);

} /**

* The main entry point for the application.

* This is the Java equivalent of Python's 'if __name__ == "__main__":'

*/

public static void main(String[] args) {

int number = 5;

// The static method is called directly on the class.

long result = MathTools.factorial(number); System.out.println(number + "! is " + result);

}

}

</code>

</program>

<p>

Notice the key differences: instead of <c>def</c>, the method signature <c>public static int</c> declares its scope, that it belongs to the class rather than an object, and that it returns an <c>int</c>. All logic is contained within curly braces <c>{}</c>.

</p>

</section>

<section xml:id="java-patterns-for-recursion">

<title>Common Recursive Patterns</title>

<p>

In many recursive algorithms, the recursive calls need extra information that the original caller shouldn’t have to provide. This could be a counter, an index into an array, or the current node in a data structure. Forcing the user to provide these initial values makes the method's public interface clumsy and error-prone.

</p>

<p>

The private helper method pattern is the standard solution. It allows us to present a clean, simple public method while the private helper handles the complex, stateful details of the recursion. The public method acts as a wrapper, performing any initial setup before calling the private helper to begin the recursive process. Let's explore this with a detailed tree traversal example.

</p>

<program interactive="activecode" language="java">

<code>

class TreeNode {

int val;

TreeNode left;

TreeNode right;

// Constructor to create a new tree node

TreeNode(int val) {

this.val = val;

this.left = null;

this.right = null;

}

}

public class TreeOperationsWithHelper {

public static int getTreeDepthAndInOrderTraversal(TreeNode root) {

// Handle the case of an empty tree before calling the helper.

if (root == null) {

System.out.println("In-order traversal: (empty tree)");

return 0; // An empty tree has a depth of 0

}

System.out.print("In-order traversal: ");

// Call the private helper method to perform the recursive traversal and depth calculation.

// The helper method will return the depth of the tree.

return inOrderTraversalAndDepthHelper(root);

}

private static int inOrderTraversalAndDepthHelper(TreeNode node) {

// Base case: If the node is null, it means we've gone past a leaf,

// so it contributes 0 to the depth.

if (node == null) {

return 0;

}

// Recursively calculate the depth of the left subtree.

// The in-order traversal visits the left child first.

int leftDepth = inOrderTraversalAndDepthHelper(node.left);

// Perform the "in-order" action for the current node: print its value.

// This demonstrates the in-order traversal aspect.

System.out.print(node.val + " ");

// Recursively calculate the depth of the right subtree.

// The in-order traversal visits the right child last.

int rightDepth = inOrderTraversalAndDepthHelper(node.right);

// The depth of the current subtree is 1 (for the current node itself)

// plus the maximum depth found in its left or right subtree.

return 1 + Math.max(leftDepth, rightDepth);

}

public static void main(String[] args) {

// --- Example Tree 1 ---

// 1

// / \

// 2 3

// / \

// 4 5

TreeNode root1 = new TreeNode(1);

root1.left = new TreeNode(2);

root1.right = new TreeNode(3);

root1.left.left = new TreeNode(4);

root1.left.right = new TreeNode(5);

System.out.println("--- Tree Operations With Helper Method ---");

int depth1 = getTreeDepthAndInOrderTraversal(root1);

System.out.println("\nDepth of Tree 1: " + depth1); // Expected In-order: 4 2 5 1 3, Depth: 3

}

}

</code>

</program>

<p>

The primary reason for using a helper function in this tree example is to separate the clean, simple "what do I want to do?" from the more complex "how do I actually do it recursively?".

</p>

<p>

The private static int <c>inOrderTraversalAndDepthHelper(TreeNode node)</c> method is where the real recursive logic resides. It's private because its job is purely to support the public method. Its parameter, <c>TreeNode</c> node, is the essential piece of state that changes with each recursive call, allowing the function to "move" through the tree.

</p>

<p>

The time and space complexity of this algorithm are important to understand. The algorithm has a time complexity of O(N), where N is the number of nodes in the tree. This is because the helper function visits every node exactly once to process it. The space complexity is determined by the maximum depth of the recursion on the call stack. This directly corresponds to the height of the tree, H. Therefore, the space complexity is O(H). In a well-balanced tree, the height is logarithmic in relation to the number of nodes, making the complexity O(logN). However, in the worst-case of a completely unbalanced (skewed) tree, the height is equal to the number of nodes, leading to a space complexity of O(N). The pattern translates directly to other languages like Python, demonstrating its fundamental utility in structuring recursive code.

</p>

<program interactive="activecode" language="python">

<code>

import math # Used for math.max, though Python's built-in max() is often preferred

# Define a simple TreeNode class for our binary tree

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class TreeOperationsWithHelper:

def get_tree_depth_and_in_order_traversal(root: 'TreeNode') -&gt; int:

# Handle the case of an empty tree before calling the helper.

if root is None:

print("In-order traversal: (empty tree)")

return 0 # An empty tree has a depth of 0

print("In-order traversal: ", end="")

return TreeOperationsWithHelper._in_order_traversal_and_depth_helper(root)

def _in_order_traversal_and_depth_helper(node: 'TreeNode') -&gt; int:

if node is None:

return 0

left_depth = TreeOperationsWithHelper._in_order_traversal_and_depth_helper(node.left)

print(node.val, end=" ")

right_depth = TreeOperationsWithHelper._in_order_traversal_and_depth_helper(node.right)

return 1 + max(left_depth, right_depth) # Using Python's built-in max()

# Provided Solution class for Pre-order Traversal (translated to Python)

class Solution:

def _preorder_traversal_helper(self, root: 'TreeNode', answer: list[int]):

if root is None:

return

answer.append(root.val)

self._preorder_traversal_helper(root.left, answer)

self._preorder_traversal_helper(root.right, answer)

def preorder_traversal(self, root: 'TreeNode') -&gt; list[int]:

answer = []

self._preorder_traversal_helper(root, answer)

return answer

# Main execution block (equivalent to Java's main method)

if __name__ == "__main__":

# --- Example Tree 1 ---

# 1

# / \

# 2 3

# / \

# 4 5

root1 = TreeNode(1)

root1.left = TreeNode(2)

root1.right = TreeNode(3)

root1.left.left = TreeNode(4)

root1.left.right = TreeNode(5)

print("--- Tree Operations With Helper Method ---")

depth1 = TreeOperationsWithHelper.get_tree_depth_and_in_order_traversal(root1)

print(f"\nDepth of Tree 1: {depth1}") # Expected In-order: 4 2 5 1 3, Depth: 3

</code>

</program>

</section>

<section xml:id="recursion-limits-in-java">

<title>Recursion Limits: Python vs. Java</title>

<p>

The consequence of deep recursion, running out of stack space, is a concept you've already encountered in Python. Java handles this in a very similar way, throwing an error when the call stack depth is exceeded.

</p>

<p>

The key difference is the name of the error:

</p>

<ul>

<li>In Python, this raises a <c>RecursionError</c>.</li>

<li>In Java, this throws a <c>StackOverflowError</c>.</li>

</ul>

<p>

Neither language supports <idx> tail call optimization </idx><term>tail call optimization</term>, so the practical limits on recursion depth are a factor in both. If an algorithm requires thousands of recursive calls, an iterative (loop-based) approach is the preferred solution in both Python and Java.

</p>

<p>

The following Python code demonstrates a situation where a function calls itself indefinitely without a base case, leading to aRecursionError.

</p>

<program interactive="activecode" language="python">

<code>

def cause_recursion_error():

"""

This function calls itself without a base case, guaranteeing an error.

"""

cause_recursion_error()

# Standard Python entry point

if __name__ == "__main__":

print("Calling the recursive function... this will end in an error!")

# This line starts the infinite recursion.

# Python will stop it and raise a RecursionError automatically.

cause_recursion_error()

</code>

</program>

<p>

The following Java code demonstrates a similar situation, where a method calls itself indefinitely without a base case, leading to a StackOverflowError.

</p>

<program interactive="activecode" language="java">

<code>

public class Crash {

public static void causeStackOverflow() {

// This method calls itself endlessly without a stopping condition (a base case).

// Each call adds a new layer to the program's call stack.

// Eventually, the stack runs out of space, causing the error.

causeStackOverflow();

}

// A main method is required to run the program.

public static void main(String[] args) {

System.out.println("Calling the recursive method... this will end in an error!");

// This line starts the infinite recursion.

causeStackOverflow();

}

}

</code>

</program>

</section>

</chapter>