Skip to main content
Practice

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 starts with 0 and 1, progressing as 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 time complexity of implementing the Fibonacci sequence using a recursive function is O(2^n). This is because the function makes two function calls at each step, leading to exponential growth in the number of calls.