Java Tail Recursion | What is Tail Recursion?

Last Updated : 26 Mar 2025

Tail recursion is a particular case of recursion where the recursive call is the last operation in the function. It allows some compilers or interpreters to optimize the recursive call to avoid consuming additional stack space, which can prevent stack overflow errors for deeply recursive calls.

Example of Tail Recursion

Let's take a look at a simple example: calculating the Fibonacci of a number using tail recursion.

Example

public class TailRecursiveFibonacci {
    // Main Method - entry point of the program
    public static void main(String[] args) {
        // Define the position in the Fibonacci sequence
        int position = 10;
        // Print the Fibonacci number at the given position using tail recursion
        System.out.println("Fibonacci number at position " + position + " is: " + fibonacci(position));
    }
    // Public Method to start the tail-recursive Fibonacci computation
    public static int fibonacci(int n) {
        // Call the helper method with initial values for the previous two Fibonacci numbers
        return fibonacciHelper(n, 0, 1);
    }
    // Private helper method to compute Fibonacci using tail recursion
    private static int fibonacciHelper(int n, int a, int b) {
        // Base case: if n is 0, return the first Fibonacci number
        if (n == 0) {
            return a;
        } else {
            // Recursive case: call the helper method with updated values
            return fibonacciHelper(n - 1, b, a + b);
        }
    }
}   

Output:

 
Fibonacci number at position 10 is: 55

Need for Tail Recursion

Tail-recursive functions are often preferred over non-tail-recursive ones due to their potential for optimization by compilers.

In recursive calls, a stack is used to store information such as parameter values. Non-tail-recursive functions increase stack depth with each call, leading to higher memory usage and risk of stack overflow.

Tail-recursive functions optimize this by making the recursive call the last operation, allowing the compiler to reuse the stack frame. It reduces memory overhead and lowers the risk of stack overflow.

Can a non-tail-recursive function be written as tail-recursive to optimize it?

Example

 
public class NonTailRecursiveFactorial {
    // Main Method - entry point of the program
    public static void main(String[] args) {
        // Define a number to calculate its factorial
        int number = 5;
        // Print the factorial of the number
        System.out.println("Factorial of " + number + " is: " + factorial(number));
    }
    //Method to compute the factorial of a number
    public static int factorial(int n) {
        // Base case: if n is 0, return 1 (factorial of 0 is 1)
        if (n == 0) {
            return 1;
        } else {
            // Recursive case: return n multiplied by the factorial of (n - 1)
            return n * factorial(n - 1);
        }
    }
}   

Output:

 
Factorial of 5 is: 120

Time Complexity: O(n)

Auxiliary Space Complexity: O(n)

In the above example, the recursive call to factorial(n - 1) is not the last operation, as a multiplication follows it.

Example

public class TailRecursiveFactorial {
    // Main Method - entry point of the program
    public static void main(String[] args) {
        // Define a number to calculate its factorial
        int number = 5;
        // Print the factorial of the number using the tail-recursive Method
        System.out.println("Factorial of " + number + " is: " + factorial(number));
    }
    // Public Method to start the tail-recursive factorial computation
    public static int factorial(int n) {
        // Call the helper method with the initial accumulator value of 1
        return factorialHelper(n, 1);
    }
    // Private helper method to compute factorial using tail recursion
    private static int factorialHelper(int n, int accumulator) {
        // Base case: if n is 0, return the accumulated result
        if (n == 0) {
            return accumulator;
        } else {
            // Recursive case: call the helper method with n-1 and update the accumulator
            return factorialHelper(n - 1, n * accumulator);
        }
    }
}   

Output:

 
Factorial of 5 is: 120

Time Complexity: O(n)

Auxiliary Space Complexity: O(1)

In the tail-recursive version, the factorialHelper Method uses an additional parameter (accumulator) to carry the intermediate result. The recursive call factorialHelper(n - 1, n * accumulator) is the last operation, making it tail-recursive.

Key Points for Conversion

Accumulator Parameter: Introduce an additional parameter to accumulate results, which allows you to pass intermediate results along with each recursive call.
Last Operation: Ensure that the recursive call is the last operation in the function. No additional computation should follow the recursive call.
State Management: Manage state or results using parameters rather than relying on post-recursive operations.

Converting a function to a tail-recursive form can make it more efficient in languages or environments that support tail-call optimization. However, it's important to note that Java does not natively optimize tail recursion, but understanding and using tail recursion can still be beneficial for designing algorithms and understanding recursion.

Next TopicHow to Enable Java in Chrome

← prev next →

We deliver comprehensive tutorials, interview question-answers, MCQs, study materials on leading programming languages and web technologies like Data Science, MEAN/MERN full stack development, Python, Java, C++, C, HTML, React, Angular, PHP and much more to support your learning and career growth.