How to find max number in an array using tail recursion in java

How to find max number in an array using tail recursion in java

Table of contents

No heading

No headings in the article.

First of all, there are better approaches for this, but this article focuses on the recursive approach, especially tail recursion(optimal)

So, what exactly is tail recursion?

Let’s understand this, in traditional recursion, we perform our recursive calls first, and during this, each recursive call gets stored in a stack. When it reaches the base case, it returns to previous calls, and each recursive call returns some values. We use these returned values to calculate the result. Also, each stored recursive call gets popped up from the stack during the backtracking.

In this manner, we don’t get the result of your calculation until we have returned from every recursive call.

The problem with this approach is that the stack size is fixed, and when there are so many calls, JVM may throw a stackoverflow error.

The solution to the above problem is tail recursion.

In tail recursion, we perform our calculations first, then execute the recursive call, passing the results of our current step to the next recursive step. This results in the last statement being in the form of

return recursive-function (params))

The return value of any given recursive step is the same as the return value of the next recursive call.

public class LargestNumber {
    public static void main(String[] args) throws Exception {
        int[] arr = new int[] {1, 10, 9, 5, 9, 4, 15, 12, 19};
        System.out.println(largestNumber(arr, arr.length, 0));
    }

    private static int largestNumber(int[] arr, int length, int result) {
        if (length == 1) return Math.max(arr[0], result);
        else return largestNumber(arr, length - 1, Math.max(arr[length - 1], result));
    }
}

In our above example, we calculate the max in each step and then pass the result as the parameter of the recursive call.

Math.max(arr[length-1],result)

Did you find this article valuable?

Support Sumant Kumar by becoming a sponsor. Any amount is appreciated!