Activité récursivité
Exercice 1: analyser un programme récursif: somme des éléments d'une liste
On considère une liste: L = [2,12,1,8,5,10,20], calculons la somme des éléments de cette liste:
La somme des termes de cette liste est: 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 final le calcul à faire est: 2+(12+(1+(8+(5+(10+(20))))))=58
Considérons une fonction appelée somme_recursive_liste(L) qui calcule et renvoie le résultat de la somme des éléments selon la méthode décrite ci-dessous:
Soit une liste L, de n nombres entier, passée en paramètre à la fonction somme_recursive_liste(L)
si la Longueur L = 1:
renvoyer L[0]
sinon:
renvoyer L[0] + somme_recursive_liste(L[1:])
Quelques rappels sur les listes:
La fonction len(liste1) renvoie le nombre d'éléments de liste1
L[1:] : créer une sous liste de L contenant les éléments de l'élément d'indice 1 jusqu'à la fin de la liste.
Si L = [2,12,1,8,5,10,20] alors L[1:] <=> [12,1,8,5,10,20] et L[0] = 2
1.1 Préciser la condition du cas de base de cette fonction
1.2 Ecrire la fonction somme_recursive_liste(L) et la tester pour plusieurs valeurs de liste.
1.3 Dessiner un schéma des appels récursifs avec le contenu de la liste à chaque étape ( s'inspirer du schéma de l'annexe1)
On considère maintenant une solution itérative ( itératif <=> boucle) obtenue avec une boucle for du même calcul :
def somme_iterative_liste(liste):
somme = 0
for i in range(len(liste)):
somme+=liste[i]
return somme
1.4 On vous donne ci-dessous un programme qui calcule la durée d'exécution du calcul de la somme pour 1000 valeurs générées aléatoirement, tester ce programme et conclure sur la technique la plus rapide entre la récursivité et l'itération:
# 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 à 2000 le nombre de récursion autorisée
import sys
sys.setrecursionlimit(2000)
# génération de 1000 nombres aléatoires
Liste=[randint(0,100) for i in range(1000)]
# 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(somme_recursive_liste(Liste))
# mesure du temps: fin de l'exécution
fin=timer()
# calcul et affichage du temps: fin - début
print("temps d'exécution de somme_liste:", fin-debut)
debut=timer()
#appel et affichage du résultat de l'exécution de la fonction itérative
print(somme_iterative_liste(Liste))
fin=timer()
print("temps d'exécution de somme_liste:" , fin-debut)
Exercice 2: analyser un programme récursif: recherche du minimum dans une liste
2.1 Ecrire une fonction appelée minimum ( nombre1, nombre2) qui renvoie le plus petit des deux nombres nombre 1 et nombre 2 passés en paramètres.
On considère maintenant une liste de n nombres entiers naturels Liste = [a0, a1,a2,...an]
Le minimum de la liste Liste est le minimum entre a0 et le minimum de la liste L0 = [a1,a2,...an] qui est lui même le minimum entre a1 et le minimum de la liste [a2,a3,...an] et ainsi de suite... La condition d’arrêt étant: s’il n’y a qu’un seul élément dans la liste alors le minimum de la liste est cet élément.
2.2 Ecrire la fonction minimum_recursive(liste) qui utilise le principe décrit précédemment pour déterminer le minimum d'une liste, on vous donne sa méthode ci-dessous, vous remarquerez qu'elle utilise votre fonction minimum.
Soit une liste, de n nombres entier, passée en paramètre à la fonction minimum_recursive(liste):
si la Longueur de cette liste = 1:
renvoyer liste[0]
sinon:
renvoyer minimum (liste[0] , minimum_recursive(liste[1:])
2.3 Tester le résultat de l'exécution avec la liste Liste = [3,12,11,8,5,10,20] en paramètre de la fonction.
On vous donne le pseudo code d'une fonction itérative appelée minimum_iterative(liste) qui fait le même travail selon un autre principe: soit une liste de n éléments: L = [a0, a1,a2,...an] que l'on passe en paramètre à la fonction, on initialise une variable de la fonction appelée mini qui représentera le minimum avec le premier nombre de la liste : mini=a0.
On parcours ensuite la liste en appelant à chaque étape: minimum( mini, L[i]) que l'on affecte à mini:
2.4 Ecrire la version python du programme ci-dessus, cette fonction utilise votre fonction minimum(nombre1,nombre2) . Tester son exécution pour L = [3,12,11,8,5,10,20].
2.5 Comparer le temps d'exécution des deux fonctions comme dans la question 2.3
Exercice 3: écrire des programmes récursifs
3.1 Écrire les versions itératives et récursives de la fonction produit (n) qui calcule le produit des nombres entiers <= n avec n >= 0
si n=0, la fonction renvoie 0, si n=1, la fonction renvoie 1
Exemples de calculs que doit effectuer la fonction:
si n=0, produit(0) = 0
si n=1, produit(1) = 1
si n=2, produit(2) = 2 x 1 = 2
si n=3, produit(3) = 3 x 2 x 1 = 6
si n=4, produit(4) = 4 x 3 x 2 x 1 = 24
3.2 Écrire les versions itératives et récursives de la fonction factorielle(n) qui calcule la factorielle de n
la factorielle de n que les mathématiciens note n! avec n un nombre entier naturel vaut n×(n−1)×(n−2)×...×2×1
n! = n×(n−1)×(n−2)×...×2×1
Remarque: par définition 0! = 1
Créé avec HelpNDoc Personal Edition: Produire des livres Kindle gratuitement