# IAL-501 (Prof. Dr. Silvio do Lago Pereira)

#-----------------------------------------------------------
# Exemplo 3
#-----------------------------------------------------------

def fat(n):
    if n==0: return 1             # base
    else:    return n*fat(n-1)    # passo

#-----------------------------------------------------------
# Exercicio 2
#-----------------------------------------------------------

def pot(x,n):
    if n==0: return 1
    else:    return pot(x,n-1) * x

#-----------------------------------------------------------
# Exercicio 3
#-----------------------------------------------------------

def termial(n):
    if n==0: return 0
    else:    return termial(n-1) + n

#-----------------------------------------------------------
# Exercicio 4
#-----------------------------------------------------------

def cr(n):
    if n==0: return
    print(n) 
    cr(n-1)

#-----------------------------------------------------------
# Exercicio 5
#-----------------------------------------------------------

def cp(n):
    if n==0: return
    cp(n-1)
    print(n)

#-----------------------------------------------------------
# Exercicio 6
#-----------------------------------------------------------

def binario(n):
    if n<2: print(n,end='')
    else: 
        binario(n//2)
        print(n%2,end='')

#-----------------------------------------------------------
# Exemplo 7
#-----------------------------------------------------------

def cro(n):
    while True:
        if n<0: return
        print(n) 
        n = n-1

#-----------------------------------------------------------
# Exemplo 8
#-----------------------------------------------------------

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

#-----------------------------------------------------------
# Exemplo 9
#-----------------------------------------------------------

def Fm(n, memo = {1:1, 2:1}):
    if n not in memo: 
       memo[n] = Fm(n-1) + Fm(n-2)
    return memo[n]