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

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 starts returning to previous calls, each recursive call returns some values, we use these returned values to calculate the end result. Also, during the backtracking, each stored recursive call gets popped up from the stack.

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 the size of the stack 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, and then we 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))

. Basically, 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 are calculating the max in each step and then passing the result as the parameter of the recursive call.

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