Рекурсивные функции

Отдельно рассмотрим рекурсивные функции. Главное отличие рекурсивных функций от обычных методов состоит в том, что они рекурсивная функция может вызывать саму себя.

Например, рассмотрим функцию, которая вычисляет факториал числа:

static int factorial(int x) {
    if (x == 1) {
        return 1;
    }
    return x * factorial(x - 1);
}

Вначале проверяется условие: если вводимое число не равно 1, то мы умножаем данное число на результат этой же функции, в которую в качестве параметра передается число x - 1. То есть происходит рекурсивный спуск. И так дальше, пока не дойдем того момента, когда значение параметра не будет равно единице.

Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и который помещается в начале функции. В случае с факториалом это if (x == 1) return 1;. И все рекурсивные вызовы должны обращаться к подфункциям, которые в конечном счете сходятся к базовому варианту. Так, при передаче в функцию положительного числа при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант.

Хотя в данном случае нужно отметить, что для определения факториала есть более оптимальные решения на основе циклов:

static int factorial(int x){
    int result = 1;
    for (int i = 1; i <= x; i++) {
        result *= i;
    }
    return  result;
}

Еще одним распространенным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. В теории n-й член последовательности Фибоначчи определяется по формуле: f(n) = f(n - 1) + f(n - 2), причем f(0) = 0, а f(1) = 1.

static int fibonachi(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    } else {
        return fibonachi(n - 1) + fibonachi(n - 2);
    }
}