What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers in which each subsequent number is the sum of the two preceding ones. Usually, the first two numbers in the sequence are 0 and 1.

Formal definition: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n > 1.

Example of the first numbers in the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Example implementation in PHP:

<?php

/**
 * Generates the n-th Fibonacci number recursively.
 * Inefficient for large n due to repeated calculations.
 *
 * @param int $n Index of the number in the sequence (starting from 0).
 * @return int The n-th Fibonacci number.
 */
function fibonacciRecursive(int $n): int
{
    if ($n <= 1) {
        return $n; // Base case: F(0)=0, F(1)=1
    }
    return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2); // Recursive call
}

/**
 * Generates the n-th Fibonacci number iteratively.
 * More efficient for large n.
 *
 * @param int $n Index of the number in the sequence (starting from 0).
 * @return int The n-th Fibonacci number.
 */
function fibonacciIterative(int $n): int
{
    if ($n <= 1) {
        return $n; // Base case
    }

    $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; // Update F(n-2)
        $b = $c; // Update F(n-1)
    }

    return $b; // Result - last computed number
}

// Usage examples
// echo fibonacciRecursive(7); // Output: 13
// echo fibonacciIterative(7); // Output: 13

?>