Отдельно рассмотрим рекурсивные функции. Главное отличие рекурсивных функций от обычных методов состоит в том, что они рекурсивная функция может вызывать саму себя.
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n. То есть по сути для нахождения факториала
числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4, а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5.
Определим метод для нахождения факториала:
int factorial(int n){
if (n == 1) return 1;
return n * factorial(n - 1);
}
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант, с которого начинается вычисление функции. В случае с факториалом это факториал числа 1, который равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта применяется оператор return:
if (n == 1) return 1;
То есть, если вводимое число равно 1, то возвращается 1
Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:
return n * factorial(n - 1);
Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.
Используем эту функцию:
class Program{
public static void main(String[] args) {
int factorial4 = factorial(4); // 24
int factorial5 = factorial(5); // 120
int factorial6 = factorial(6); // 720
System.out.printf("Факториал числа 4 = %d\n", factorial4);
System.out.printf("Факториал числа 5 = %d\n", factorial5);
System.out.printf("Факториал числа 6 = %d\n", factorial6);
}
static int factorial(int n){
if (n == 1) return 1;
return n * factorial(n - 1);
}
}
Рассмотрим поэтапно, что будет в случае вызова factorial(4).
Сначала идет проверка, равно ли число единице:
if (n == 1) return 1;
Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код
return n * factorial(n - 1);
То есть фактически мы имеем:
return 4 * factorial(3);
Далее выполняется выражение:
factorial(3)
Опять же n не равно 1, поэтому выполняется код
return n * factorial(n - 1);
То есть фактически:
return 3 * factorial(2);
Далее выполняется выражение:
factorial(2)
Опять же n не равно 1, поэтому выполняется код
return n * factorial(n - 1);
То есть фактически:
return 2 * factorial(1);
Далее выполняется выражение:
factorial(1)
Теперь n равно 1, поэтому выполняется код
if (n == 1) return 1;
И возвращается 1.
В итоге выражение
factorial(4)
В реальности выливается в
4 * 3 * 2 * factorial(1)
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: fib(n)=fib(n-1) + fib(n-2), причем fib(0)=0, а fib(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... Для определения чисел этой последовательности определим следующий метод:
class Program{
public static void main(String[] args) {
int fib4 = fib(4);
int fib5 = fib(5);
int fib6 = fib(6);
System.out.printf("4 число Фибоначчи = %d\n", fib4);
System.out.printf("5 число Фибоначчи = %d\n", fib5);
System.out.printf("6 число Фибоначчи = %d\n", fib6);
}
static int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
}
Здесь базовый вариант выглядит следующий образом:
if (n == 0 || n == 1) return n;
То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число - 0 или 1. Иначе возвращается
результат выражения fib(n - 1) + fib(n - 2);
Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:
static int fib2(int n)
{
int result = 0;
int b = 1;
int tmp;
for (int i = 0; i < n; i++){
tmp = result;
result = b;
b += tmp;
}
return result;
}
В то же время в некоторых ситуациях рекурсия предоставляет элегантное решение, например, при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.