PHP Program for Fibonacci Using Recursion

You can write a PHP function using recursion to find Fibonacci numbers like this: function fibonacci($n) { if ($n <= 1) return $n; return fibonacci($n - 1) + fibonacci($n - 2); }.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return it directly because these are the base cases. Otherwise, calculate the sum of the Fibonacci numbers at positions n-1 and n-2 by calling the function recursively.

Algorithm

1

Check if the input number is 0 or 1; if yes, return the number.

2

Otherwise, call the function recursively for the previous two numbers.

3

Add the results of the two recursive calls.

4

Return the sum as the Fibonacci number for the input.

Code

php

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

echo fibonacci(10);
?>

Output

55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, call fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

5

Call fibonacci(1) and fibonacci(0)

Return 1 and 0 respectively

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Function Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(3)	2
fibonacci(4)	3
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns the input number directly if it is 0 or 1 using if ($n <= 1) return $n;. This stops the recursion.

Step 2: Recursive Calls

For numbers greater than 1, the function calls itself twice to get the two previous Fibonacci numbers using fibonacci($n - 1) + fibonacci($n - 2).

Step 3: Sum and Return

The function adds the results of the two recursive calls and returns the sum as the Fibonacci number for $n.

Alternative Approaches

Iterative approach

php

<?php
function fibonacci_iterative($n) {
    if ($n <= 1) return $n;
    $a = 0;
    $b = 1;
    for ($i = 2; $i <= $n; $i++) {
        $temp = $a + $b;
        $a = $b;
        $b = $temp;
    }
    return $b;
}

echo fibonacci_iterative(10);
?>

This uses a loop instead of recursion, which is faster and uses less memory.

Memoization (caching results)

php

<?php
function fibonacci_memo($n, &$cache = []) {
    if ($n <= 1) return $n;
    if (isset($cache[$n])) return $cache[$n];
    $cache[$n] = fibonacci_memo($n - 1, $cache) + fibonacci_memo($n - 2, $cache);
    return $cache[$n];
}

echo fibonacci_memo(10);
?>

This stores results to avoid repeated calculations, improving speed for large inputs.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive function calls itself twice for each number greater than 1, leading to exponential growth in calls, so time complexity is O(2^n).

Space Complexity

The maximum depth of the recursion stack is n, so space complexity is O(n) due to function call overhead.

Which Approach is Fastest?

The iterative approach is fastest with O(n) time and O(1) space. Memoization improves recursion to O(n) time but uses extra memory for caching.

Approach	Time	Space	Best For
Recursive (simple)	O(2^n)	O(n)	Learning recursion, small inputs
Iterative	O(n)	O(1)	Performance and memory efficiency
Memoization	O(n)	O(n)	Large inputs with recursion style