# 5) Récursivité croisée

def pair(n):
    if n == 0:
        return True
    else:
        return impair(n-1)

def impair(n):
    if n == 0:
        return False
    else:
        return pair(n-1)

assert not pair(5) and impair(5)

# 6) Récursivité multiple – Suite de Fibonacci

def Fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)
        
assert Fibonacci(5) == 8

# 7) Récursivité multiple – Triangle de pascal (coefficients binomiaux)

def Pascal(n, k):
    if n == k or k == 0:
        return 1
    else:
        return Pascal(n - 1, k - 1) + Pascal(n-1, k)
        
assert Pascal(5, 2) == 10 and Pascal(5, 3) == 10 

# 8) Hors programme - Récursivité terminale

def somme_terminal(n, acc = 0):
    if n == 0: 
        return acc
    else:
        return somme_terminal(n-1, acc + n)

assert somme_terminal(10) == 55

def produit_terminal(a, b, acc=0):
    if a == 0:
        return acc
    elif a < 0:
        return produit_terminal( a+1, b, acc - b) 
    else:
        return produit_terminal( a-1, b, acc + b)

assert produit_terminal(123, 456) == 123*456
assert produit_terminal(-123, 456) == -123*456

def puissance_terminal(n, exp, acc=1):
    if n == 0 and exp == 0:
        pass # indéfini mathématiquement
    if n == 0:
        return 0
    if exp == 0:
        return acc
    elif exp < 0:
        return puissance_terminal(n, exp + 1, acc/n)
    else:
        return puissance_terminal(n, exp - 1, acc*n)

assert puissance_terminal(123, 4) == 123**4
assert puissance_terminal(-2, -4) == 0.0625

# 9) Bonus : Tribonacci, programmation dynamique, mémoïsation
# 1)
def tribonacci(n):
    if n == 0 or n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)

assert tribonacci(6) == 7

# Si on dessine l'arbre d'appel, plusieurs branches sont identitiques et sont calculées plusieurs fois.
# Par exemple, tribonacci(6) appelle tribonacci(5) et tribonacci(4). tribonacci(5) appelle aussi tribonacci(4).

# 2) 

def tribonacci_iter(n):
    l = [0, 0, 1]
    if n < 3:
        return l[n]
    else:
        for i in range(3, n+1):
            l.append(l[-1] + l[-2] + l[-3])
    return l[-1]
    
assert tribonacci_iter(6) == 7

# 3)
 
def tribonacci_memo(n, d = {}) :
    if n == 0 or n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        if n not in d:
            d[n] = tribonacci_memo(n-1, d) + tribonacci_memo(n-2, d) + tribonacci_memo(n-3, d)
        return d[n]
      
assert tribonacci_memo(6) == 7