Recursion is a technique in computer programming that involves solving a problem by breaking it down into smaller sub-problems, and solving each of these sub-problems individually. This process of repeatedly breaking down a problem into smaller sub-problems can be done through a technique called Recursion.
Recursive functions are functions which call themselves directly, or indirectly through another function. In this article, we will explore recursion in Java in depth, including how it works internally in the stack.
What is Recursion?
Recursion is a technique of solving a problem by breaking it down into smaller sub-problems, and solving each of these sub-problems individually. This process is done by defining the problem in terms of one or more smaller versions of itself. In other words, recursion involves defining a problem in terms of itself or smaller sub-problems.
A recursive function consists of the following two parts:
Base Case
Recursive Case
Base Case
The base case is the smallest version of the problem that can be solved without recursion, and this is where the recursion terminates. The base case is the termination condition that stops the recursion.
Recursive Case
The recursive case is where the problem calls itself with one or more smaller versions of the problem, which are then solved recursively until the base case is reached. In other words, it is the actual recursive call that causes the function to call itself again and again.
Recursion Example in Java
Let's explore a simple example of recursion in Java. Consider the factorial function, which takes a positive integer as input and returns the factorial of that number. The factorial of a number is the product of all positive integers up to and including that number. For example, the factorial of 5 is 5 4 3 2 1 = 120.
Here is an implementation of the factorial function using recursion in Java:
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
In the example above, the base case is when n equals 0, in which case the function returns 1. The recursive case is when n is greater than 0, in which case the function calls itself with n - 1 as the argument. This keeps happening until n reaches 0, which is then returned to the caller.
How Recursion Works in Java
When a function calls itself, a new instance of that function is created and pushed onto the stack. Each instance of the function holds its own set of parameters and local variables, and its own execution context. This is referred to as a stack frame.
As the function call stack grows, it becomes a LIFO (Last-In-First-Out) stack, similar to a stack of blocks. When a function completes execution and returns a value, its stack frame is removed from the top of the stack and discarded. The returned value is used for whatever purpose it is needed, such as storing in a variable, or using in a mathematical calculation.
As the algorithm approaches its base case, the stacks start getting popped out and the recursion unwraps. This means that as we finish computing the result of a smaller version of the problem, we return it and the stack slowly unwinds until we get back to the original invocation of the function.
If we take the example of the factorial function, to find the factorial of 5, the function calls itself as factorial(4) with n=4. Then factorial(3) with n=3, and so on, until factorial(1) with n=1. Once the base case is reached, it returns 1 and moves back up the recursion stack, calculating the product of each recursion level until it reaches the original invocation of factorial(5) and returns the final result of 120.
Stack Overflow
It's worth noting that recursive functions can potentially cause a stack overflow error, because each recursive call adds its own entry to the call stack, which is a finite resource. In other words, if the recursion is too deep or too time-consuming, it can require more memory than available on our stack.
Tail Recursion Optimization
Tail recursion occurs when the recursive call is at the end of the function, and the rest of the function code after the recursive call is not used in the calculation of the result.
The tail recursion optimization is an optimization technique to improve the performance of recursive calls, and avoid the risk of stack overflow by avoiding extra recursive stack frames. This optimization is possible if the function operation does not depend on the result of the recursive call.
Java doesn't provide tail recursion optimization by default, but it is still possible to manually optimize tail recursive functions using an iterative approach.
Example of Tail Recursion in Java
Let's consider the factorial function again, but with a tail recursion approach, using an additional helper function.
public static int factorialTailRec(int n) {
return factorialWithAccumulator(n, 1);
}
public static int factorialWithAccumulator(int n, int accumulator) {
if (n == 0) {
return accumulator;
}
return factorialWithAccumulator(n - 1, n * accumulator);
}
Instead of calling factorialWithAccumulator recursively, it passes the result of the recursive call to the current invocation of factorialWithAccumulator. This eliminates the need for a new stack frame for each recursive call, and improves performance and saves memory.
Now, we call the factorialTailRec function instead of the original factorial function to get the tailored recursive approach.
Conclusion
Recursion is a powerful technique in programming that allows you to solve complex problems by breaking them down into smaller sub-problems. With every recursive call, a new instance of a function is created and it pushes a new stack frame into the call stack.
Recursion provides a compact and elegant solution to many problems in programming, but it can also have some limitations, including the potential risk of stack overflow errors.
However, tail recursion optimization can provide an optimized way to solve this, by avoiding unnecessary recursive function calls and eliminating unneeded stack frames, thus improving performance and saving memory.