How to calculate Fibonacci in PHP

Introduction

The Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, known as Fibonacci. In PHP, this sequence can be generated in several ways, including iterative, recursive, and using closed-form expressions. We’ll explore multiple implementations to demonstrate how you can calculate Fibonacci numbers in PHP, analyze their efficiencies, and discuss the best use cases for each method.

Basic Recursive Method

<?php
function fibonacciRecursive($n)
{
    if ($n <= 1) {
        return $n;
    } else {
        return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
    }
}

// Example usage
echo fibonacciRecursive(10); // Output: 55
?>

This basic recursive function is a direct translation of the Fibonacci sequence definition into PHP code. However, this method is very inefficient for large numbers due to its exponential time complexity caused by the repeated recalculations of the same Fibonacci numbers.

Iterative Method

<?php
function fibonacciIterative($n)
{
    $fib = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }
    return $fib[$n];
}

// Example usage
echo fibonacciIterative(10); // Output: 55
?>

This iterative method is more efficient than the recursive one, as it reduces the time complexity to linear by avoiding redundant calculations. It builds up the Fibonacci series by looping and storing all intermediate results in an array.

Memorization method (Top-down Dynamic Programming)

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

// Example usage
echo fibonacciMemoized(10); // Output: 55
?>

This approach, also known as the top-down dynamic programming approach, adds a memorization mechanism to the basic recursive method. It avoids redundant calculations by storing previously calculated Fibonacci numbers in an array and reusing them when needed.

Dynamic Programming Method (Bottom-up Tabulation)

<?php
function fibonacciDP($n)
{
    if ($n <= 1) {
        return $n;
    }
    $fib = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }
    return $fib[$n];
}

// Example usage
echo fibonacciDP(10); // Output: 55
?>

This method is similar to the iterative approach but is a bottom-up version of the memorization method. Instead of starting from the top, it builds up the solution from the base case upwards, consequently this method is essentially similar to the iterative one and often can be used interchangeably, with the difference lying in the perspective of the approach.

Calculating Fibonacci Numbers Using Binet’s Formula

<?php
function fibonacciBinet($n)
{
    $sqrt5 = sqrt(5);
    $phi = (1 + $sqrt5) / 2;
    return round(pow($phi, $n) / $sqrt5);
}

// Example usage
echo fibonacciBinet(10); // Output: 55
?>

Binet’s formula allows for a closed-form expression to find the nth Fibonacci number without iterating or recursion. It uses the golden ratio and the square root of 5 to calculate the number directly. However, due to the use of floating-point arithmetic, it can suffer from precision issues for very large values of ‘n’.

Conclusion

PHP offers various methods to calculate Fibonacci numbers, from basic recursive functions to sophisticated mathematical expressions like Binet’s formula. When choosing the right approach, consider the trade-off between code simplicity and performance, especially when calculating large Fibonacci numbers. As a rule of thumb, avoid using simple recursion for large sequences and prefer iterative or dynamic programming methods to keep performances in check.