Activité récursivité
Exercice 1: écrire et analyser un programme récursif
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
On veut écrire 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, le principe sera:
si la longueur de L vaut 1, il faut renvoyer L[0] sinon il faut renvoyer L[0] + somme_recursive_liste(L[1:])
L[1:] crée la sous liste de L contenant les éléments de l'élément d'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[1:] est placé comme argument de la fonction somme_recursive_liste ce qui provoque un appel récursif avec une nouvelle liste privée du premier élément et ainsi de suite jusqu'à ce que le cas de base soit atteint.
1.1 Préciser le cas de base de cette fonction ( le cas de base est celui qui permet d'arrêter les appels récursifs)
1.2 Ecrire la fonction somme_recursive_liste(L) et la tester pour la liste L = [2,12,1,8,5,10,20] donnée en exemple .
1.3 Dessiner un tableau de l'évolution du code avec les appels récursifs (voir les exemples dans le cours) pour la liste
L = [2,12,1]
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 d'une liste de 1000 nombres générés aléatoirement, tester ce programme et conclure sur la technique la plus rapide pour calculer la somme 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 de la durée d'exécution de la fonction: fin - début
print("temps d'exécution de somme_liste:", fin - debut)
# nouvelle mesure du temps
debut = timer()
# appel et affichage du résultat de l'exécution de la fonction itérative
print(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)
Exercice 2:
Conception d'une fonction de recherche du minimum dans une liste de manière récursive et itérative
2.1 Ecrire une fonction appelée minimum ( nombre1, nombre2) qui renvoie le plus petit des deux nombres nombre1 et nombre2 passés en arguments.
2.2 On considère maintenant une liste de n nombres entiers naturels L = [a0, a1, a2,..., an]
Le minimum de la liste L est le minimum entre a0 et le minimum du reste de la liste L0 = [a1, a2,..., an] qui est lui même le minimum entre a1 et le minimum du reste de la liste L1 = [a2, a3,..., an] et ainsi de suite... La condition d’arrêt étant que s’il n’y a qu’un seul élément dans la liste L alors le minimum de la liste est cet élément.
- 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 la méthode ci-dessous, vous remarquerez qu'elle utilise votre fonction minimum de la question 2.1
Soit la fonction minimum_recursive(liste) qui reçoit en argument une liste de n nombres entiers
si la Longueur de liste vaut 1, la fonction doit renvoyer liste[0] ; sinon la fonction doit renvoyer le résultat de minimum ( liste[0] , minimum_recursive(liste[1:]))
- Tester le résultat de l'exécution avec la liste L = [ 3,12,11, 8, 5, 10, 20 ] en argument de la fonction.
On vous donne ci-dessous le pseudo code d'une fonction itérative appelée minimum_iterative(L) qui fait le même travail selon cet autre principe:
soit une liste de n éléments: L = [a0, a1, a2,..., an] que l'on passe en argument à la fonction; dans la fonction, on initialise une variable appelée mini qui représentera un minimum fictif 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 pour 1000 données comme dans la question 1.4
Exercice 3: écrire un programme récursif
Écrire les versions itératives et récursives de la fonction produit (n) qui calcule le produit des nombres entiers inférieurs ou égal à n avec n supérieur ou égal à 0.
Exemples de calculs que doit effectuer la fonction:
si n=0, la fonction renvoie 0, si n=1, la fonction renvoie 1
si n=0, produit(0) renvoie 0
si n=1, produit(1) renvoie 1
si n=2, produit(2) renvoie 2 x 1 = 2
si n=3, produit(3) renvoie 3 x 2 x 1 = 6
si n=4, produit(4) renvoie 4 x 3 x 2 x 1 = 24
Pour ceux en avance:
Exercice 4:
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éfinition 0! vaut 1
ainsi:
1! vaut 1
2! vaut 2x1
3! vaut 3x2x1
Écrire les versions itératives et récursives de la fonction factorielle(n) qui calcule la factorielle de n
Remarque: la fonction factorielle(n) est différente de la fonction produit(n) parce que produit(0) vaut 0 alors que factorielle(0) vaut 1
Créé avec HelpNDoc Personal Edition: Produire des livres Kindle gratuitement