#!/usr/bin/python3
# Různé způsoby výpočtu Fibonacciho čísel

### Čistá rekurzivní verze, exponenciálně pomalá

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

### Rekurze s pamětí na už spočítané výsledky, složitost O(n)

pamet = { 0: 0, 1: 1 }

def fib1(n):
    if n not in pamet:
        pamet[n] = fib1(n-1) + fib1(n-2)
    return pamet[n]

### Iterativní řešení

def fib2(n):
    p = [0] * (n+1)
    p[1] = 1
    for i in range(2, n+1):
        p[i] = p[i-1] + p[i-2]
    return p[n]

### Iterativní řešení s konstantní pamětí

def fib3(n):
    if n < 2:
        return n
    a, b = 0, 1
    for i in range(1, n):
        a, b = b, a+b
    return b