Objectifs

Consignes

Pile d'exécution

A faire vous même

Analysez puis testez le programme suivant :


def fctA():
	print ("Début fonction fctA")
	i=0
	while i<5:
		print("fctA",i)
		i = i + 1
	print ("Fin fonction fctA")

def fctB():
	print ("Début fonction fctB")
	i=0
	while i<5:
		if i==3:
			fctA()
		print ("Retour à la fonction fctB")
		print ("fctB",i)
		i = i + 1
		print ("Fin fonction fctB")

fctB()

Vous devriez obtenir l'enchainement suivant : 


		Début fonction fctB
		fctB 0
		fctB 1
		fctB 2
		Début fonction fctA
		fctA 0
		fctA 1
		fctA 2
		fctA 3
		fctA 4
		Fin fonction fctA
		Retour à la fonction fctB
		fctB 3
		fctB 4
		Fin fonction fctB

Dans l'exemple ci-dessus, nous avons une fonction (fctB) qui appelle une autre fonction (fctA). La principale chose à retenir de cet exemple est que l'exécution de fctB est interrompue pendant l'exécution de fctA. Une fois l'exécution de fctA terminée, l'exécution de fctB reprendra là où elle avait été interrompue.

Pour gérer ces fonctions qui appellent d'autres fonctions, le système utilise une "pile d'exécution". Une pile d'exécution permet d'enregistrer des informations sur les fonctions en cours d'exécution dans un programme. On parle de pile, car les exécutions successives "s'empilent" les unes sur les autres. Si nous nous intéressons à la pile d'exécution du programme étudié ci-dessus, nous obtenons le schéma suivant :

Nous pouvons "découper" l'exécution de ce programme en 3 parties :

  1. la fonction fctB s'exécute jusqu'à l'appel de la fonction fctA
  2. l'exécution de la fctB est mise en "pause" pendant l'exécution de la fonction fctA
  3. une fois que l'exécution de fctA est terminée, on termine l'exécution de la fonction fctB

Il est important de bien comprendre que la fonction située au sommet de la pile d'exécution est en cours d'exécution. Toutes les fonctions situées "en dessous" sont mises en pause jusqu'au moment où elles se retrouveront au sommet de la pile. Quand une fonction termine son exécution, elle est automatiquement retirée du sommet de la pile (on dit que la fonction est dépilée).

La pile d'exécution permet de retenir la prochaine instruction à exécuter au moment où une fonction sera sortie de son ""état de pause" (qu'elle se retrouvera au sommet de la pile d'exécution) :

Évidemment l'explication donnée ci-dessus est quelque peu simpliste : c'est l'adresse mémoire de la prochaine instruction machine à exécuter qui est conservée dans la pile d'exécution.

Dans l'exemple ci-dessus, on retrouve une variable i dans les deux fonctions : fctA et fctB. La variable i présente dans la fonction fctA n'a rien à voir avec la variable i présente dans la fonction fctB (elles portent le même nom, mais elles représentent 2 adresses mémoires différentes). Il est très important de bien comprendre que les variables créées dans une fonction ne "sortent" pas de la fonction : chaque fonction possède sa propre liste de variable, comme déjà dit ci-dessus la variable i de la fonction fctB est différente de la variable i de la fonction fctA.

La pile d'exécution conserve une "trace" des valeurs des variables lorsqu'une autre fonction est exécutée. Par exemple la valeur de i (fctB) est conservée au moment de l'exécution de fctA. Quand l'exécution de fctA se termine est que l'exécution de fctB "reprend", la valeur référencée par i (fctB) a été "conservée" (voilà pourquoi on reprend l'exécution de fctB avec un "fctB 3").

Fonction récursive

Une fonction peut s'appeler elle-même, on parle alors de fonction récursive.

A faire vous même

Analysez puis testez le programme suivant :


def fctA():
	print ("Hello")
	fctA()
fctA()

Comme vous pouvez le constater, nous avons une erreur dans la console Python : 


		RecursionError: maximum recursion depth exceeded while calling a Python object

Dans le cas où une fonction s'appelle elle-même (fonction récursive), on retrouve le même système de pile d'exécution. Dans l'exemple traité ci-dessus, les appels s'enchainent sans rien pour mettre un terme à cet enchainement, la taille de la pile d'exécution augmente sans cesse (aucune fonction ne termine son exécution, nous n'avons pas de "dépilement" juste des "empilements"). Le système interrompt le programme en générant une erreur quand la pile d'exécution dépasse une certaine taille.

Quand on écrit une fonction récursive, il est donc nécessaire de bien penser à mettre en place une structure qui à un moment ou à un autre mettra fin à ces appels récursifs.

Dans le cas de fonctions récursives, il est, comme pour n'importe quelle fonction, possible d'utiliser des paramètres :

A faire vous même

Essayez de prévoir le résultat de l'exécution du programme ci-dessus. Vérifiez votre hypothèse en exécutant le programme.


def fonct(n):
  if n>0:
      fonct(n-1)
  print(n)

fonct(3)

Essayons de comprendre en détail ce qui se passe dans le programme ci-dessus :

Voici un schéma expliquant le processus en termes de pile d'exécution :

Il ne faut jamais perdre de vu qu'à chaque nouvel appel de la fonction fonct le paramètre n est différent.

Voici un lien permettant de visualiser la gestion de la pile d'exécution pour ce programme récursif avec Python Tutor

Quelques exemples classiques de fonctions récursives

Factorielle

Nous allons étudier le calcul de la factorielle grâce à une fonction récursive. D'après Wikipédia : "En mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n". Par exemple : la factorielle de 3 est : 3 x 2 x 1 = 6 ; la factorielle de 4 est 4 x 3 x 2 x 1 = 24 ; la factorielle de 5 est 5 x 4 x 3 x 2 x 1 = 120 ...

Si on note la factorielle de n par n!, on a :

Ecrire une fonction non récursive nommée factorielle_iterative(n) qui calcule et retourne n! en utilisant une boucle.

Ecrire une fonction récursive nommée factorielle_recursive(n) qui calcule et retourne n! sans utiliser une boucle.

Comme vous pouvez le constater, la fonction fact est structurée de la même manière que la définition mathématique vu ci-dessus :

L'utilisation des fonctions récursives est souvent liée à la notion de récurrence en mathématiques :

En mathématiques une suite définie par récurrence est une suite définie par son premier terme et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu'ils existent.

La suite de Fibonacci

La fonction récursivefactorielle_recursive() est dite une fonction simplementrécursive car la formule de récurrence ne fait intervenir que le terme précédent.

Il existe des suites définies en mathématiques avec une récurrence dite double, ou triple (ou plus généralement multiple).

Un exemple très connu de suite définie par une récurrence double est la suite de Fibonacci.

Cette suite nommée u est définie comme suit :

Ce qui nous donne pour les 6 premiers termes de la suite de Fibonacci :

Ecrire deux fonctions fibonacci_iterative(n) et fibonacci_recursive(n)qui calculent et retournent le terme de rang n de la suite de Fibonacci.

Etude de la comparaison de l'efficacité des deux fonctions

  1. En terme de durée d'exécution

    En utilisant la méthode time du module time qui permet de calculer la durée d'exécution d'une partie d'un programme, comparer les durées d'exécution des fonctions fibonacci_iterative(n) et fibonacci_recursive(n) pour des valeurs de n définies par n = 2i pour i allant de 0 à 8.

    Voici un exemple d'utilisation de time

    
timestamp1 = time.time()
val = fibonacci_iteratif(1024)
timestamp2 = time.time() - timestamp1

  2. En terme de nombre de boucles ou bien de nombre d'appels récursifs

    Modifiez les deux fonctions en introduisant un compteur de boucle pour la fonction fibonacci_iterative(n) et un compteur du nombre d'appels à la fonction fibonacci_recursive(n).

Donner une explication sur les différences observées.

Vous donnerez notamment l'ordre de grandeur de la complexité algorithmique des deux versions itérative et récursive du calcul d'un terme de la suite de Fibonacci.

Vous pouvez vous aider de la ressource suivante : ici.

Transformation d'un algorithme itératif en algorithme récursif

Nous allons reprendre l'exemple de l'algorithme de rendu de pièces avec une méthode de résolution dite gloutonne et dans une version itérative. 


def rendu_pieces_algorithme_glouton(somme,S):
    ind = 0
    pieces_rendues = []
    while somme != 0:
        while S[ind] <= somme:
            pieces_rendues.append(S[ind])
            somme -= S[ind]
        if somme != 0:
            if ind == len(S)-1:
                return -1
            else:
                ind += 1
    return pieces_rendues

Voici une version possible de la même fonction dans une version récursive : 


def rendu_pieces_algorithme_glouton_recur(somme,S,pieces_rendues=[],ind=0):
	if somme == 0:
	    return pieces_rendues
	elif S[ind] <= somme:
	    return rendu_pieces_algorithme_glouton_recur(...., S, ...., ind)
	elif ind == len(S)-1:
	    return -1
	else:
	    return rendu_pieces_algorithme_glouton_recur(...., S, ...., ....)

Explications :

Les paramètres de la fonction rendu_pieces_algorithme_glouton_recur sont :

Remplacez les ..... par les paramètres d'appel récursif qui conviennent.

Et tester (avec doctest ) votre programme avec les systèmes monétaires suivants :

Des utilisations "artistiques" et "ludiques" de la récursivité

Le module Turtle qui permet de dessiner

A faire vous même

Étudiez le Wikibook consacré au module Turtle (wikibook Turtle) afin d'acquérir les bases de ce module.

A faire vous même

Essayez de prévoir le résultat de l'exécution du programme ci-dessus. Vérifiez votre hypothèse en exécutant le programme.


		import turtle as t
		t.forward(100)
		t.left(120)
		t.forward(100)
		t.left(120)
		t.forward(100)

Testez le programme ci-dessous et écrire une version récursive de la fonction dessin() nommée dessin_recursif().


from turtle import *

couleurs = ['blue','green','yellow','orange','red','purple']
bgcolor('black')

def dessin():
    for i in range(180):
        color(couleurs[i%6])
        forward(i)
        right(59)
    done()

dessin()
Une figure fractale : le flocon de Von Koch

A faire vous même

Visionnez la vidéo consacrée au flocon de Koch :

A faire vous même

Voici un programme Python à compléter qui construit le flocon de Von Koch. 


import turtle as t

def koch(longueur, n):
if n == 0:
	t.forward(longueur)
else:
koch(...., n-1)
	t.left(..)
	koch(...., n-1)
	t.right(..)
	koch(...., n-1)
	t.left(..)
	koch(...., n-1)


def flocon(taille, etape):
	koch(taille, etape)
	t.right(..)
	koch(taille, etape)
	t.right(...)
	koch(taille, etape)

flocon(100, 3)

A partir des informations obtenues sur la construction du flocon de Von-Koch, remplacez les pointillés par ce qu'il faut pour générer la figure fractale.

Pour découvrir d'autres fractales

Vous pouvez consulter cette ressource sur des animations avec des figures fractales : ici.

Un exemple ludique utilisant la récursivité : les tours de Hanoï
Tour de Hanoï

Essayez de résoudre ce jeu avec 4 disques (ou plus), à partir de cette animation.

A faire vous même

Consulter le diaporama suivant qui donne des explications sur l'algoritme doublement récursif qui permet de résoudre le jeu des tours de Hanoï avec un nombre quelconque de disques :

diaporama resolution tour de Hanoi

Auteur : Hugues Malherbe (basé sur un document de David Roche)