Рекурсия

Рекурсивные функции в java — это функции, которые вызывают сами себя. Их следует использовать осторожно, так как, к примеру, если не задать условие выхода из функции, то произойдёт переполнение стека вызовов (StackOverflowError).

Есть два важных для понимания рекурсии определения :

  • Базис рекурсии — условие выхода из блока рекурсивных вызовов, базисное решение задачи, когда нет необходимости вызывать рекурсию
  • Шаг рекурсии — вызов функцией самой себя при изменении параметров

Классическим примером рекурсии является вычисление факториала от числа. Базисом рекурсии в данном случае будет вычисление факториала от 1 (либо если на вход изначально подан 0 либо отрицательное число). Шагом будет вычисление факториала от N-1.

Пример рекурсивного решения задачи :

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Или другой пример (с более красивым выводом) :

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Вперед

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *