Трудно точно определить компромиссы, связанные с рекурсией.
На математически абстрактном уровне рекурсия дает мощную основу для описания явного поведения функции.Например, мы можем математически определить факториал как
x! = 1 if x == 0
x! = x * (x - 1)! else
Или мы можем рекурсивно определить более сложную функцию, например, как мы можем вычислить «N выбрать K»:
C(n, k) = 1 if k == 0
C(n, k) = 0 if k < 0 or if n > k
C(n, k) = C(n - 1, k) + C(n - 1, k - 1) else
Когдаиспользуя рекурсию в качестве метода реализации, нет никакой гарантии, что вы в конечном итоге будете использовать больше памяти или создавать код, который работает более эффективно.Часто рекурсия использует больше места из-за памяти, необходимой для хранения кадров стека, но в некоторых языках это не проблема, поскольку компилятор может попытаться оптимизировать вызовы функций (см., Например, исключение хвостовых вызовов).В других случаях рекурсия может израсходовать огромные ресурсы до такой степени, что рекурсивный код может не завершиться при простых задачах.
Что касается вопросов эффективности, часто рекурсивный код существенно менее эффективен, чем итеративный код.Вызовы функций дороги, а наивный перевод из рекурсии в код приводит к ненужному дублированию работы.Например, наивная реализация Фибоначчи
int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
ужасно неэффективна и настолько медленна, что никогда не использовалась на практике.Хотя код чище, неэффективность поглощает любые потенциальные преимущества рекурсии.
В других случаях, однако, рекурсия может удивительно сэкономить время.Например, mergesort - это очень быстрый алгоритм сортировки, определяемый красивой рекурсией:
Mergesort(array, low, high) {
if (low >= high - 1) return;
Mergesort(array, low, low + (high - low) / 2);
Mergesort(array, low + (high - low) / 2, high);
Merge(array, low, low + (high - low) / 2, high);
}
Этот код очень быстрый, и соответствующий итерационный код, вероятно, будет медленнее, труднее для чтения и труднее для понимания.
Короче говоря, рекурсия не является ни магическим лекарством, ни силой, которой следует избегать.Это помогает осветить структуру многих проблем, которые в противном случае могут показаться трудными или почти невозможными.Хотя это часто приводит к более четкому коду, оно часто делает это за счет времени и памяти (хотя это не обязательно автоматически менее эффективно; во многих случаях это может быть более эффективно).Определенно стоит учиться совершенствовать свои навыки алгоритмического мышления и решения проблем, даже если вы никогда не пишете в своей жизни еще одну рекурсивную функцию.
Надеюсь, это поможет!