###########################################
###########################################
## TP 07 : Récursivité
###########################################
###########################################

## Importations

import sys
sys.setrecursionlimit(100000)

## Exercice 1 : suite arithmétique

def arithmetique(n,a0,d) :
    if n == 0 :
        return a0
    else :
        return arithmetique(n-1,a0,d) + d

assert arithmetique(0,5,3) == 5
assert arithmetique(4,5,3) == 17

## Exercice 2 : suite géométrique

def geometrique(n,u0,r) :
    if n == 0 :
        return u0
    else :
        return geometrique(n-1,u0,r) * r

assert geometrique(0,5,3) == 5
assert geometrique(4,5,3) == 405

## Exercice 3 : une somme arithmétique

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

n = 20
assert somme_suite(n) == n*(n+1) // 2

## Exercices 4/5 : suite récurrente linéaire d'ordre 2

def fibonacci(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

assert fibonacci(10) == 55

# on constate que le calcul de fibonacci(38) est assez long.
# Cela s'explique par le fait que la fonction fibonacci
# s'appelle elle-même 2 fois à chaque étape, donc cela conduit
# à un nombre d'opérations qui croît exponentiellement.


## Exercice 6 : liste créée récursivement

def liste_consec(n) :
    if n == 1 :
        return [1]
    else :
        return liste_consec(n-1) + [n]

assert liste_consec(5) == [1,2,3,4,5]

## Exercice 7 : somme des éléments d'une liste

def somme(L) :
    if len(L) == 0 :
        return 0
    else :
        premier = L[0]
        L2 = L[1:]
        return somme(L2) + premier

assert somme([1,4,2,-5]) == 2

## Exercice 8 : produit des éléments d'une liste

def produit(L) :
    if len(L) == 0 :
        return 1
    else :
        premier = L[0]
        L2 = L[1:]
        return produit(L2) * premier

assert produit([1,4,2,-5]) == -40

## Exercice 9 : inversion d'une chaîne de caractères

def inverser(C) :
    if len(C) == 0 :
        return ''
    else :
        premier = C[0]
        C2 = C[1:]
        return inverser(C2) + premier

assert inverser("abeille") == "ellieba"

## Exercice 10 : longueur d'une chaîne

def longueur(C) :
    if C == "" :
        return 0
    else :
        C2 = C[1:]
        return longueur(C2) + 1

assert longueur("abracadabra") == 11

## Exercice 11 : détection des palindromes

def est_palindrome(C) :
    if len(C) < 2 :
        return True
    else :
        n = len(C)
        if C[0] != C[n-1] :
            return False
        else :
            return est_palindrome(C[1:n-1])

assert est_palindrome('kayak')
assert not est_palindrome('voilier')

def palindrome2(C) :
    return C == inverser(C)

## Exercice 12 : maximum d'une liste

def maxi(L) :
    if len(L) == 1 :
        return L[0]
    else :
        m1 = L[0]
        m2 = maxi(L[1:])
        if m1 < m2 :
            return m2
        else :
            return m1

assert maxi([5,4,-3,8,7,2]) == 8

## Exercice 13 : coefficients binomiaux

def k_parmi_n(k,n) :
    if k == 0 :
        return 1
    if k > n :
        return 0
    return k_parmi_n(k,n-1) + k_parmi_n(k-1,n-1)

assert k_parmi_n(5,10) == 252

## Exercice 14 : liste de sous-listes

def sous_listes(L) :
    if len(L) == 0 :
        return [[]]
    else :
        a = L[-1]
        M = sous_listes(L[:-1])
        N = []
        for ssliste in M :
            N.append(ssliste + [a])
        return M + N