Как найти максимальное число в массиве с помощью хвостовой рекурсии в java

Что именно представляет собой хвостовая рекурсия?

Давайте разберемся, в традиционной рекурсии мы сначала выполняем рекурсивные вызовы, и во время этого каждый рекурсивный вызов сохраняется в стеке. Когда он достигает базового варианта, он начинает возвращаться к предыдущим вызовам, каждый рекурсивный вызов возвращает некоторые значения, мы используем эти возвращенные значения для вычисления конечного результата. Кроме того, во время обратного хода каждый сохраненный рекурсивный вызов поднимается из стека.

Таким образом, мы не получим результат вычисления, пока не вернемся из каждого рекурсивного вызова.

Проблема такого подхода заключается в том, что размер стека фиксирован, и при большом количестве вызовов JVM может выдать ошибку переполнения стека.

Решением этой проблемы является хвостовая рекурсия.

При хвостовой рекурсии мы сначала выполняем вычисления, а затем выполняем рекурсивный вызов, передавая результаты нашего текущего шага следующему рекурсивному шагу. В результате последний оператор будет иметь вид

 return recursive-function (params))
Войти в полноэкранный режим Выйти из полноэкранного режима

. В принципе, возвращаемое значение любого данного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова.

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));
    }
}
Войти в полноэкранный режим Выход из полноэкранного режима

В нашем примере мы вычисляем максимальное значение на каждом шаге, а затем передаем результат в качестве параметра рекурсивного вызова.

Math.max(arr[length-1],result)
Войти в полноэкранный режим Выход из полноэкранного режима

Оцените статью
Procodings.ru
Добавить комментарий