Implementing Fibonacci Sequence with Recursive Function

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones.

It typically begins with 0 and 1, forming the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The Fibonacci numbers can be mathematically defined as F(n) = F(n-1) + F(n-2), and can be implemented in Python as follows:

Fibonacci Sequence Implementation

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Time Complexity

The recursive Fibonacci function has a time complexity of O(2^n). Since each call spawns two new calls, the number of calls grows exponentially.