NSI - Terminale - Récursivité

Travail demandé

Partie 1: Analyser un programme récursif

Question 1.1

Calcul de la somme des nombres d'un tableau ( méthode récursive)

On considère un objet liste ( un tableau de nombres) assigné à la variable L:
L = [2,12,1,8,5,10,20], calculons la somme des éléments de cette liste.
La somme des termes de cette liste peut s'écrire: 2+( la somme des termes de [12,1,8,5,10,20]) soit: 2+(12+(la somme des termes de [1,8,5,10,20]) et ainsi de suite jusqu’à: 2+(12+(1+(8+(5+(10+( la somme des termes de [20])))))), la somme des termes de [20] est 20.

Au ﬁnal le calcul à faire est: 2+(12+(1+(8+(5+(10+(20)))))) = 58

On veut écrire la définition de la fonction somme_recursive_liste(L) qui calcule et renvoie le résultat de la somme des éléments de L selon la méthode décrite ci-dessus.

L'algorithme que doit contenir la fonction:

si la longueur de L vaut 0, il faut renvoyer None
si la longueur de L vaut 1, il faut renvoyer L[0]
sinon il faut renvoyer L[0] + somme_recursive_liste(L[1:])

Explication de la partie sinon de l'algorithme:

L[1:] vaut la sous liste de L contenant les éléments de l'indice 1 jusqu'à la fin de la liste.
Pour L = [2,12,1,8,5,10,20] alors L[1:] vaut [12,1,8,5,10,20] alors que L[0] vaut 2.
l'expression return L[0] + somme_recursive_liste(L[1:]) devient ici return 2 + somme_recursive_liste([12,1,8,5,10,20]), c'est le code python du calcul 2+( la somme des termes de [12,1,8,5,10,20]) expliqué ci-dessus.
Vous remarquerez que L[1:] est placé comme argument de la fonction somme_recursive_liste dans la partie "sinon" de l'algorithme, ce qui provoque un appel récursif (rappel) du code de la fonction avec une nouvelle liste sans le premier élément et ainsi de suite jusqu'à ce que le cas de base soit atteint.
Le cas de base est atteint quand la longueur de la liste vaut 1 ( il suffit alors de renvoyer cet élément, pas d'appels récursifs)

Ecrire la définition de la fonction somme_recursive_liste(L) qui utilisera l'algorithme décrit précédemment.
Tester la fonction pour la liste L = [2,12,1,8,5,10,20] donnée en exemple.
Dessiner un tableau de l'évolution du code avec les appels récursifs (voir l'exemple dans le chapitre Ressources) pour la liste L = [2,12,1]

Question 1.2

Compléter la définition de la fonction test() qui vérifie que la fonction somme_recursive_liste(L) donne le bon résultat pour une liste L donnée. Vous utiliserez pour ça des assertions, vous devez tester ce que renvoie la fonction pour une liste L vide, pour une liste d'un seul élément et pour une liste quelconque. Par exemple, voici l'assertion qui teste le résultat d'une liste avec un seul élément passée en argument à la fonction:
```
 # définition de la fonction de test: 
 def test():
     # l'appel de la fonction pour la liste [20] doit donner 20
     assert somme_recursive_liste([20]) == 20
     # ajouter vos tests ci-dessous:

     # si toutes les assertions sont franchies, on affiche un message:
     print("assertions OK")
 # utilisation de la fonction de test:
 test()
```

Question 1.3

Calcul de la somme des nombres d'un tableau ( méthode itérative)

Compléter la définition de la fonction somme_iterative(L) qui calcule la somme des éléments d'un tableau de nombres assigné à l'argument L, de manière itérative ( avec une boucle qui parcourt la liste assignée à L):

 # définition de la fonction: 
 def somme_iterative(L):
     somme = 0
     # ajouter votre code ci-dessous:

     # la fonction renvoie la somme
     return somme

 # utilisation de la fonction:
 t = [2,12,1,8,5,10,20]
 print("la somme vaut:", somme_iterative(t))

Rappel: ici on appelle la fonction en passant la variable t comme argument, c'est l'équivalent de demander somme_iterative([2,12,1,8,5,10,20]) ce qui veut dire que l'argument L de la définition vaut dans ce cas [2,12,1,8,5,10,20]

Partie 2: Comparer les performances d'une fonction récursive et d'une fonction itérative

Dans cette partie vous allez mesurer le temps de calcul des deux fonctions précédentes pour un grand nombre de données dans le tableau.

Principe

On vous donne un code python qui génère aléatoirement 2000 nombres dans un tableau puis appelle chacune des fonctions pour effectuer la somme de ces nombres. Le code calcule le temps d'exécution de chaque fonction en comparant le temps écoulé entre le moment où est lancée la fonction et le moment où elle donne son résultat :

# import de fonctions des modules  timer et random
from timeit import default_timer as timer
from random import randint
# import du module sys pour augmenter à 5000 le nombre de récursion autorisée
import sys  
sys.setrecursionlimit(5000)
# définition de la fonction itérative: 
def somme_iterative_liste(L):
    if len(L) == 0:
        return None
    somme = 0
    # ajouter votre code ci-dessous:
    for x in L:
        somme += x
    # la fonction renvoie la somme
    return somme
 # définition de la fonction récursive: 
def somme_recursive_liste(L):
    if len(L) == 0:
        return None
    elif len(L) == 1:
        return L[0]
    else:
        return L[0] + somme_recursive_liste(L[1:])
# génération de 1000 nombres aléatoires
Liste = [randint(0,100) for i in range(2000)]
# mesure du temps: début de l'exécution
debut=timer()
# appel et affichage du résultat de l'exécution de la fonction récursive
print( "la somme recursive vaut:", somme_recursive_liste(Liste) )
# mesure du temps: fin de l'exécution
fin = timer()
# calcul et affichage de la durée d'exécution de la fonction: fin - début
print("temps d'exécution de somme_liste:", fin - debut, "secondes")
# nouvelle mesure du temps
debut = timer()
# appel et affichage du résultat de l'exécution de la fonction itérative
print("la somme itérative vaut:", somme_iterative_liste(Liste))
# mesure du temps: fin de l'exécution 
fin = timer()
# calcul et affichage de la durée d'exécution de la fonction: fin - début 
print("temps d'exécution de somme_liste:" , fin-debut,"secondes")

Question 2.1

tester le code python et conclure sur la fonction la plus efficace.

Partie 3: écrire un programme récursif

Soit n un nombre entier naturel, on appelle factorielle de n, que l'on note n!, le produit n×(n−1)×(n−2)×...×2×1

n! = n×(n−1)×(n−2)×...×2×1

Par déﬁnition 0! vaut 1

ainsi:

1! vaut 1 soit 1 x 0!

2! vaut 2x1 soit 2 x 1!

3! vaut 3x2x1 soit 3 x 2!

n! = n x (n-1)!

Question 3.1

Écrire une version itérative et une version récursive de la définition de la fonction factorielle(n) qui calcule et renvoie la factorielle de n
Écrire une fonction test_fact() qui vérifie que la fonction factorielle(n) donne le bon résultat pour plusieurs valeurs de n. Vous utiliserez pour ça des assertions ( revoir question 1.2), vous devez tester ce que renvoie la fonction pour n=0 et pour une nombre n quelconque.