HEAD & TAIL RECURSION
Head and tail recursion are two types of recursive functions. In head recursion, the recursive call is the first thing that happens in the function, while in tail recursion, the recursive call is the last thing that happens in the function.
In some cases, the compiler can optimize tail recursion to turn it into an iteration, which can be more efficient in terms of memory usage and call stack depth. However, the same optimization is not possible for head recursion.
To optimize tail recursion, the compiler can use a technique called tail call optimization. When a tail recursive function is called, instead of creating a new stack frame, the current frame is reused. This means that the function can be executed in a loop, rather than creating new stack frames for each recursive call.
This optimization can be particularly useful for recursive functions that make a large number of recursive calls, as it can reduce the memory usage and improve the performance of the function. However, not all compilers support tail call optimization, so it may not always be possible to take advantage of this optimization technique.
Head recursion, on the other hand, cannot be optimized in the same way, as each recursive call creates a new stack frame that must be maintained until the function completes. However, it is still a useful technique in some cases, particularly for functions that need to process data in a specific order, such as tree traversals.
HEAD RECURSION
public static int sum(int n) {
// Base case
if (n == 0) {
return 0;
}
// Recursive step
return n + sum(n - 1);
}
In the example above, the sum method is implemented using head recursion. It takes an integer n as input and returns the sum of the first n numbers. The base case is when n is zero, and the recursive step is adding n to the sum of the first n-1 numbers.
TAIL RECURSION
public static int sum(int n, int acc) {
// Base case
if (n == 0) {
return acc;
}
// Recursive step
return sum(n - 1, acc + n);
}
In the example above, the sum method is implemented using tail recursion. It takes two integers as input: n, which is the current number, and acc, which is the accumulated sum so far. The base case is when n is zero, and the recursive step is passing n-1 and acc+n to the next call. In this way, the result is computed in a single step when the base case is reached, without the need to backtrack.