Что такое последовательность Фибоначчи?

Последовательность Фибоначчи — это числовая последовательность, в которой каждое последующее число является суммой двух предыдущих. Обычно первые два числа в последовательности равны 0 и 1.

Формальное определение: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) при n > 1.

Пример первых чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Пример реализации на PHP:

<?php

/**
 * Генерирует n-е число Фибоначчи рекурсивно.
 * Неэффективно для больших n из-за повторных вычислений.
 *
 * @param int $n Индекс числа в последовательности (начиная с 0).
 * @return int n-е число Фибоначчи.
 */
function fibonacciRecursive(int $n): int
{
    if ($n <= 1) {
        return $n; // Базовый случай: F(0)=0, F(1)=1
    }
    return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2); // Рекурсивный вызов
}

/**
 * Генерирует n-е число Фибоначчи итеративно.
 * Более эффективно для больших n.
 *
 * @param int $n Индекс числа в последовательности (начиная с 0).
 * @return int n-е число Фибоначчи.
 */
function fibonacciIterative(int $n): int
{
    if ($n <= 1) {
        return $n; // Базовый случай
    }

    $a = 0; // F(n-2)
    $b = 1; // F(n-1)

    for ($i = 2; $i <= $n; $i++) {
        $c = $a + $b; // F(n) = F(n-2) + F(n-1)
        $a = $b; // Обновляем F(n-2)
        $b = $c; // Обновляем F(n-1)
    }

    return $b; // Результат - последнее вычисленное число
}

// Примеры использования
// echo fibonacciRecursive(7); // Вывод: 13
// echo fibonacciIterative(7); // Вывод: 13

?>