lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def fibonacci(n):
    if n <= 1: # Base condition
        return n
    else:
        # The nth Fibonacci number = (n-1)th Fibonacci number + (n-2)th Fibonacci number
        return fibonacci(n-1) + fibonacci(n-2)

print('fibonacci(10):', fibonacci(10))

# 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:

```python title="Fibonacci Sequence Implementation"
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)
```

<br />

## 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.