Ответ
Для вычисления чисел Фибоначчи в продакшене итеративный подход предпочтительнее рекурсивного из-за кардинальной разницы в производительности и потреблении памяти.
1. Рекурсивная реализация (наивная):
Проста для понимания, но имеет экспоненциальную временную сложность O(2^n) и линейную глубину рекурсии O(n), что приводит к переполнению стека или крайне долгому выполнению даже для относительно небольших n (например, 50).
function fibRecursive(int $n): int {
if ($n <= 1) {
return $n;
}
return fibRecursive($n - 1) + fibRecursive($n - 2);
}
// Неэффективно: fibRecursive(40) вызовет ~1.1 млрд рекурсивных вызовов.2. Итеративная реализация: Имеет линейную временную сложность O(n) и константное потребление памяти O(1). Это оптимальное решение для большинства практических задач.
function fibIterative(int $n): int {
if ($n <= 1) {
return $n;
}
$prev = 0; // F(0)
$curr = 1; // F(1)
for ($i = 2; $i <= $n; $i++) {
$next = $prev + $curr;
$prev = $curr;
$curr = $next;
}
return $curr;
}
// Эффективно: вычисляет fibIterative(100) почти мгновенно.3. Продвинутые оптимизации:
- Рекурсия с мемоизацией (кешированием): Снижает сложность до O(n), но требует дополнительной памяти O(n) для хранения результатов и все равно имеет риск переполнения стека.
- Использование формулы Бине или матричного возведения в степень: Позволяет достичь сложности O(log n), что критически важно для вычисления очень больших чисел Фибоначчи (например, с индексами в миллионы).
Вывод: Для собеседования лучше показать понимание проблемы и предложить итеративное решение как базовое, упомянув более сложные методы как оптимизацию для специфических случаев.
