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

Числа Фибоначчи — это классическая целочисленная последовательность, где каждое последующее число равно сумме двух предыдущих. Стандартное определение начинается с F₀ = 0 и F₁ = 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Формула: Fₙ = Fₙ₋₁ + Fₙ₋₂, где n ≥ 2.

Сравнение подходов к вычислению на PHP:

1. Наивная рекурсия (неэффективно, O(2ⁿ)):

   function fibRecursive(int $n): int {
       if ($n <= 1) return $n;
       return fibRecursive($n - 1) + fibRecursive($n - 2);
   }
   // Не подходит для n > 40 из-за экспоненциального времени.

2. Итеративный метод (оптимально по памяти, O(n)):

   function fibIterative(int $n): int {
       if ($n <= 1) return $n;
       $prev = 0; // F₀
       $curr = 1; // F₁
       for ($i = 2; $i <= $n; $i++) {
           $next = $prev + $curr;
           $prev = $curr;
           $curr = $next;
       }
       return $curr;
   }
   echo fibIterative(10); // 55

3. Рекурсия с мемоизацией (O(n)):

   function fibMemo(int $n, array &$memo = []): int {
       if ($n <= 1) return $n;
       if (!isset($memo[$n])) {
           $memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo);
       }
       return $memo[$n];
   }

Практическое замечание: Для вычисления очень больших чисел Фибоначчи (например, F₁₀₀₀) необходимо использовать библиотеки для работы с большими числами, такие как bcmath или gmp в PHP, так как значения быстро выходят за пределы стандартного целочисленного типа.