> For the complete documentation index, see [llms.txt](https://ryotokuro.gitbook.io/problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryotokuro.gitbook.io/problems/problems1/fibonacci-easy.md).

# Fibonacci

## Iterative: O(n)

Single for loop

```python
a = 0  # starting num
b = 1

for _ in n:
    print(b)
    c = a + b
    a = b
    b = c
    
return b  # b is the second component of the fibonacci
```

## Recursive: O(2^n)

Creates 2^n (b^n where b is the number of child branches) calls to the stack at time, since the recursive call continues traversing until it reaches the base case.

```python
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    # recurse until n reaches 1
    return fibonacci(n-2) + fibonacci(n-1)
```