Функция Фибоначчи
Условие
Напишите функцию, которая вычисляет n-ое число Фибоначчи.
Числа Фибоначчи - это последовательность, в которой каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Требования
- Функция должна принимать целое число n
- Возвращать n-ое число Фибоначчи
- Реализовать рекурсивный и итеративный вариант
- Оценить сложность каждого подхода
Пример
fibonacci(7); // 13
fibonacci(10); // 55
Комментарии (1)
Ответ сгенерирован нейросетью и может содержать ошибки
Решение
Рекурсивный подход
Самый простой и интуитивный способ реализации, прямо следующий определению Фибоначчи:
function fibonacciRecursive(int $n): int {
// Базовые случаи
if ($n <= 1) {
return $n;
}
// Рекурсивное вычисление
return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
}
Характеристики рекурсивного подхода:
- Временная сложность: O(2^n) - экспоненциальная
- Пространственная сложность: O(n) - из-за стека вызовов
- Проблема: огромное количество повторных вычислений
Для n=7 функция вычислит fibonacciRecursive(6) и fibonacciRecursive(5), а fibonacciRecursive(5) вычислится дважды. Это ведёт к катастрофическому замедлению при больших n.
Итеративный подход
Более эффективная реализация через цикл:
function fibonacciIterative(int $n): int {
// Базовые случаи
if ($n <= 1) {
return $n;
}
$prev = 0; // F(0)
$current = 1; // F(1)
// Вычисляем от 2 до n
for ($i = 2; $i <= $n; $i++) {
$next = $prev + $current;
$prev = $current;
$current = $next;
}
return $current;
}
Характеристики итеративного подхода:
- Временная сложность: O(n) - линейная
- Пространственная сложность: O(1) - константная память
- Преимущество: намного быстрее для больших n
Оптимизированный рекурсивный подход (мемоизация)
Чтобы сохранить простоту рекурсии, но улучшить производительность:
function fibonacciMemo(int $n, array &$memo = []): int {
// Проверяем, есть ли результат в кеше
if (isset($memo[$n])) {
return $memo[$n];
}
// Базовые случаи
if ($n <= 1) {
return $n;
}
// Сохраняем результат перед возвратом
$memo[$n] = fibonacciMemo($n - 1, $memo) + fibonacciMemo($n - 2, $memo);
return $memo[$n];
}
Характеристики:
- Временная сложность: O(n) - каждое число вычисляется один раз
- Пространственная сложность: O(n) - для хранения кеша и стека
Сравнение подходов
| Подход | Время | Память | Использование |
|---|---|---|---|
| Рекурсия | O(2^n) | O(n) | Только для демонстрации |
| Итерация | O(n) | O(1) | Лучший выбор для production |
| Мемоизация | O(n) | O(n) | Баланс простоты и скорости |
Примеры использования
echo fibonacciIterative(7); // 13
echo fibonacciIterative(10); // 55
// Для рекурсии - только для малых n
echo fibonacciRecursive(7); // 13 (медленно)
echo fibonacciRecursive(10); // 55 (очень медленно)
Рекомендация
Для production используй итеративный подход - он самый быстрый, требует минимум памяти и идеально масштабируется. Рекурсивный подход хорош для обучения и демонстрации принципов, а мемоизация - отличный средний вариант, если важна читаемость кода.