def factorial_loop(N):
    res = 1
    for i in range(2,N):
        res *= i
    return res

def factorial_recursion(N):
    if N <= 1:
        return 1
    return N*factorial_recursion(N-1)

def euclid_loop(a,b):
    if a < b:
        a,b = b,a
    while b != 0:
        a, b = b, a%b
    return a

def euclid_recursion(a, b):
    if b > a:
        a, b = b, a
    if b == 0:
        return a
    return euclid_recursion(b, a % b)

def fibonacci_recursion(N):
    if N == 1 or N == 2: 
        return 1
    return fibonacci_recursion(N-1) + fibonacci_recursion(N-2)


def list_sum_rec1(S):
    if len(S) == 1:
        return S[0]
    return S[0] + list_sum_rec1(S[1:])
        
def list_sum_rec2(S):
    if len(S) == 1:
        return S[0]
    half = len(S)//2
    return  list_sum_rec2(S[:half])+ list_sum_rec2(S[half:])

#1 + 2 + 3 ... n
def sum1ton(n):
    if n == 1:
        return 1
    return sum1ton(n-1) + n


def reverse(s):
    if len(s) == 0:
        return ""
    return reverse(s[1:]) + s[0]

def palindrom(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return palindrom(s[1:-1])

def letterfrequency(s, letter):
    if len(s)==0:
        return 0
    if s[0] == letter:
        return 1 + letterfrequency(s[1:],letter)
    return letterfrequency(s[1:],letter)

def zip(s1, s2):
    if len(s1) == 0:
        return s2
    if len(s2) == 0:
        return s1
    return s1[0] + s2[0] + zip(s1[1:], s2[1:])


def fibonacci(N, dict):
    if N == 1 or N == 2:
        return 1
    return fibonacci(N-1) + fibonacci(N-2)

def fibonacci_save(N, dict):
    if N not in dict.keys():
        dict[N] = fibonacci_save(N-1, dict) + fibonacci_save(N-2,dict)
    return dict[N]



my_dict = {1:1,2:1}
print(fibonacci_save(10, my_dict), my_dict.values())