[]Java developers often use algorithms to break down a problem into smaller chunks that are easier to solve. This divide-and-conquer approach makes it so that, to solve each broken problem, you can call the same function multiple times to process each part.
[]In programming, recursion occurs when a method calls itself, and terminates when a base case is reached. A base case is a conditional statement that executes a return statement instead of calling the same function again, ending the cycle. Typical uses for recursion include divide-and-conquer algorithms and solving problems that occur in series, such as computing Fibonacci sequences or factorials.
[]In this post, we’ll discuss recursion in Java, and how to write a recursive method calculating the factorial of a number. You’ll see how to use recursion in Java, when it’s better than other approaches, and best practices when implementing recursive functions.
Using Recursion in Java
[]The code used for recursion in Java is relatively simple, especially compared to an iterative approach. Recursion helps you write software that uses less memory because the variables are removed as soon as the function returns. Recursive functions are pure, meaning their outputs depend on only their input parameters.
Recursion and Factorials
[]One of the simplest ways to understand recursion in Java is by examining a function that prints the factorial of a number.
[]You calculate factorials by multiplying a number with all positive integers less than itself. In this section, you’ll see the comparison between the recursive code and the code based on the loop.
[]For example, the factorial of 5 is 120, which you can express like this:
[]factorial (5) = 5 * (4 * (3 * (2 * 1)))
[]Note how this forms a series: The factorial of 5 equals 5 multiplied by the factorial of 4, 4 multiplied by the factorial of 3, and so on. The base case for the recursion is 0. You would return 1 from the method body when the input parameter reaches 0.
Factorials Using a Loop
[]The following function computes the factorial of the number passed as a parameter — once using a For loop and then again using recursion. Call this method in the main entry point and pass a parameter. You can test this by providing 5 as the input parameter, upon which the program returns 120.
[]You can use both For and While loops to perform factorials in Java. For the sake of demonstration, this example uses the For loop.
[] public static int getFactorialForLoop(int number) { int result = number; if (number >= 1) { for (int i = number – 1; i >= 1; i–) { result = result * i; } return result; } else { System.out.println(“number has to be positive”); return 1; } }
Factorials using Recursion
[]Next, let’s try using recursion to perform the same task.
[] public static int getFactorialRecursively(int number){ if (number <= 1){ return 1; } else { return number * getFactorialRecursively(number - 1); } }
[]As you can see, the code written using recursion is much cleaner than code using a For loop, and cleaner code is prone to fewer errors. In the recursion, you must only define the base and recursive cases.
[]Where possible, recursion offers plenty of advantages and some disadvantages, which we’ll discuss later on.
Handling Edge Cases
[]When building recursive functions, you can add edge cases to short-circuit the recursion. Short-circuiting tests if the next recursion call will be a base case. Instead of only returning 1 when the number is equal to or less than 0, you can return 2 when the number is equal to 2 and start the recursion.
[]Remember that short-circuiting requires writing a wrapper function that performs a conditional check on the parameters. This is often discouraged because the wrapper’s value needs to be higher.
[]To handle the short-circuiting, add a new member method to the class as a wrapper for the recursive function. The wrapper function factorial calls the internal method factorialRecursive to start the recursion. This code has the same output but skips one more step in the execution as it short-circuits when the number becomes 2.
[] private int factorialRecursive(int number) { if (number <= 1) { return 1; } return factorialRecursive(number - 1) * number; } private int factorial(int number) { if (number == 2) { return 2; } else { return factorialRecursive(number); } }
Advantages and Disadvantages of Recursion
[]Let’s now examine some of the factors in deciding between recursive and non-recursive approaches using the method in the “Recursion and Factorials” section.
Advantages of Recursion
[]In Java, recursion improves performance in several ways, including:
Memoization
[]Memoization skips recursion cases where the output has already been calculated and stored in memory. This prevents repetition of the computation because the output is stored and improves the performance of the software. This approach leverages a cache to improve performance using recursion.
[]The code to find factorials uses a cache variable to store the previously used values.
[] static int[] cache = new int[1000]; static int MemoizedFactorial(int number) { if (number <= 1) return number; if (cache[number] != 0) return cache[number]; else { cache[number] = MemoizedFactorial(number - 1) + MemoizedFactorial(number - 2); return cache[number]; } }
[]Furthermore, recursive methods also depend on inputs alone and contain business logic without underlying technical aspects such as stack management. This allows engineers to write software with less memory and fewer side effects (state changes outside the method’s scope, such as system parameters).
[]Moreover, it’s useful for specific algorithms, such as tree traversal. The depth-first search algorithm uses a stack to perform the search. Due to this, you can write the algorithm as a recursive function, which is easy to write compared to the iterative approach. For example, compare the code of pre-order traversal using the recursion versus the iterative approach.
Pre-order Traversal Using Recursion
[] public void PreOrder(Node node) { if (node != null) { visit(node.value); PreOrder(node.left); PreOrder(node.right); } }
Pre-order Traversal Using Iteration
[] public void PreOrderWithoutRecursion() { Stack < Node > stack = new Stack < Node > (); Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.pop(); visit(current.value); if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } }
[]Finally, some expressions, notably used in mathematical operations, have a particular notation. The most common notations for the input to these operations are pre-fix, infix, and post-fix. The fixation is the placement of the operand in an operation. This allows recursive functions to replicate the operation easily without additional wrappers. You can use the above expressions to build up trees from arrays and vice versa. This helps to represent complex data structures, such as a tree, in a one-dimensional memory structure, such as RAM.
Disadvantages of Recursion
[]Recursion also has its limitations. First, a recursive function repeatedly calls itself, which can cause the stack to overflow with arguments and the program to terminate prematurely. In Java, the stack space is limited for each program, whereas the heap is less limited. Therefore, when a program tries to use a lot of stack space, it receives a StackOverflowException, where a program continues to push to stack but doesn’t pop and reaches the limit.
[]The heap on the other hand is not a last-in last-out operation (LIFO), so a program can push to the heap as much as the system allows.
[]Furthermore, the Java compiler can’t optimize recursive methods that use tail recursion, when a recursive function performs a function call as the last statement. In contrast, the recursive function executes the function call as the first statement in a head recursion.
[]The code in the “Handling Edge Cases” section demonstrates that none of the functions are tail recursions. The factorialRecursion is a non-tail-recursion (not to be confused with head recursion) because it operates as the result of a function.
[]For example, you can write the factorial function you examined earlier using an iterative approach:
[] private int factorial(int number) { int factorial = 1; for (int i = 2; i <= number; i++) { factorial = factorial * i; } return factorial; }
[]This method uses a variable to store the product of all the numbers. It runs a loop that starts with the variable i set to 2 and returns the product. Note that numbers larger than 2 must be multiplied until i equals the number parameter itself. The iteration stops when the condition for the loop is met.
[]The iterative style makes it easier to define the iteration count, memory management, and when the computation stops. This also allows more control over the stack growth. It helps avoid the StackOverflowException in Java programs.
[]Similarly, iterative methods don’t require wrapper functions. Therefore, they avoid any unwanted additional stack inputs. This is why short-circuiting the recursion to gain a one-off performance improvement is often discouraged.
[]However, iterative approaches are often more cumbersome to write for series-based problems, such as computing factorials or Fibonacci sequences. Recursion generally yields a more elegant approach that produces the same results with fewer lines of code.
Recursion Best Practices
[]In a recursive function, handle all the possible edge cases to return from a recursive function. If you don’t handle the edge cases, your recursion might run forever, causing your program to terminate prematurely due to a StackOverflowException error. Short-circuiting in recursion is not always the best approach because you often have to write a wrapper function around the recursive function. Instead of a short-circuit wrapper function, apply a conditional check for the edge cases inside the recursive method and the parameters the function can accept.
[]Furthermore, remember that stacks don’t keep track of arguments already processed. This can lead your recursive function to process the same arguments repeatedly. To avoid this repetition and reduce time complexity, you should always use memoization to store arguments after processing.
How Recursion Works in Java
[]Recursive functions allow code in Java programs to call itself, computing the output by running the same operations on a series of input arguments. The examples covered are only a fraction of their real-world applications. Various searching and sorting algorithms in Java Software Development Kit (SDK) use recursion, including depth-first search, merge sort, and tree traversal.
[]That’s not to say that recursion is the end-all-be-all method, especially where memory is limited. In such scenarios, using an iterative approach to writing functions is recommended. This makes solutions more scalable and less prone to memory overflows.
[]However, recursion enables software engineers to utilize the best practices of functional programming and apply them to object-oriented programming without side effects. It’s a method that works smarter, not harder.
