Looking for java Keywords? Try Ask4Keywords

Java Language Основная идея рекурсии


пример

Что такое рекурсия:

В общем, рекурсия - это когда функция вызывает себя, прямо или косвенно. Например:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Условия применения рекурсии к задаче:

Существуют две предпосылки для использования рекурсивных функций для решения конкретной проблемы:

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

  2. Каждый уровень рекурсии должен пытаться решить меньшую проблему. Таким образом, рекурсивная функция делит проблему на более мелкие и мелкие части. Предполагая, что проблема конечна, это обеспечит завершение рекурсии.

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

пример

Следующая функция вычисляет факториалы с использованием рекурсии. Обратите внимание, как метод factorial вызывает себя внутри функции. Каждый раз, когда он называет себя, он уменьшает параметр n на 1. Когда n достигает 1 (базовое условие), функция не будет углубляться.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Это не практический способ вычисления факториалов в Java, поскольку он не учитывает переполнение целого числа или переполнение стека вызовов (например, исключения StackOverflowError ) при больших значениях n .