Рекурсия — это техника, при которой функция вызывает саму себя. Такие функции называются рекурсивными функциями.
В отличие от циклов, рекурсивные вызовы не просто повторяются один за другим. Вместо этого каждый вызов создаёт новый слой работы, и функция продолжает решать меньшие версии той же задачи, пока не достигнет простого случая, на который можно ответить напрямую.
Этот простой случай называется базовым случаем.
Начнём с функции факториала.
Мы знаем, что:
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Так что если мы уже знаем, как вычислить , то можем вычислить , умножив его на .
Это естественным образом приводит к рекурсивному решению.
Теперь рассмотрим задачу нахождения суммы всех чисел от до .
Мы можем определить её рекурсивно:
Так что, чтобы вычислить сумму до , мы сначала вычисляем сумму до , затем добавляем .
Последовательность Фибоначчи определяется следующим образом:
Так что каждое значение зависит от двух предыдущих. Это определение можно напрямую перевести в рекурсию.
Предположим, мы хотим вычислить , где — целое число, а — неотрицательное целое число.
Прямое рекурсивное определение:
Тогда рекурсивная реализация:
Это работает за время .
Мы можем улучшить предыдущий метод.
Если чётное, то:
Так что вместо уменьшения показателя на каждый раз, мы можем иногда уменьшать его вдвое. Это даёт гораздо более быстрое рекурсивное решение.
Временная сложность этой версии — , потому что на многих шагах мы делим показатель на вместо вычитания .
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int sum(int n) {
if (n == 0) {
return 0;
} else {
return n + sum(n - 1);
}
}
int F(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return F(n - 1) + F(n - 2);
}
}
int Pow(int a, int n) {
if (n == 0) {
return 1;
} else {
return a * Pow(a, n - 1);
}
}
int Pow(int a, int n) {
if (n == 0) {
return 1;
} else if (n % 2 == 0) {
int A = Pow(a, n / 2);
return A * A;
} else {
return a * Pow(a, n - 1);
}
}