Chapitre 4 : Récursivité

1 - Introduction

Dans un programme, une fonction récursive est une fonction qui s’appelle elle-même

                   

Visionnez la 1ère partie de la vidéo jusqu'à 11min35. Lien si indisponible

2 - Exemple :

def fct_recursive(i): print ("Début fonction") if i<1: print ("Fin fonction") else : print("i =",i) fct_recursive(i-1) print("Retour fonction") print ("i =",i) fct_recursive(3)

Exécuter le code

• Quelle est la condition de fin de la fonction ?
• Appeler la fonction récursive 10000 fois. Avant d'exécuter le programme, ouvrir le gestionnaire des taches et observez l'évolution de la taille mémoire occupée par votre navigateur Internet lors de l'exécution du programme.

Résumez vos constatations ci-dessous :

La récursivité est gourmande en mémoire car on doit empiler toutes les données (variables, adresses de retour, ...) avant l'appel de la fonction récursive. On parle d'une pile d'exécution. Ces valeurs seront dépilées lors du retour. Notez que la variable i est une variable locale de chaque fonction. La taille de la pile est limitée par l'espace mémoire alloué ici par le navigateur Internet qui est de l'ordre de 5000. Cette taille peut être augmentée avec l'instruction suivante :

import sys
sys.setrecursionlimit('Taille')

Non reconnue sur ce site

3 - Hello world de la récursivité

Définition : La factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Cette opération est notée avec un point d'exclamation, n!.

Une boucle for permet de résoudre le problème, mais nous allons résoudre le problème de manière récursive

Exemple : 5! = 5*4*3*2*1

Avant de programmer on commence par identifier le cas de fin ici : si n=1 alors on renvoie 1

Algorithme :

Fonction factorielle
paramètres :
	n : un entier strictement positif et supérieur à 1
retourne :
	le résultat du calcul

début
	si n≤1 alors retourner 1
	sinon retourner n*factorielle(n-1)
fin

Simulation pour n=3

factorielle (3)
	retourne 3 * factorielle (3-1)
		retourne 2 * factorielle (2-1)
			retourne 1	(n==1 condition de fin)
		2 * 1
	3 * 2 * 1
retourne (6)

Principe de fonctionnement de la pile

Traduire en langage python l'algorithme et testez la fonction

Exécuter le code

Exercice 1 ★

Réaliser à l’aide d’une fonction récursive le dessin suivant :

un colimaçon

Cahier des charges

• L'arrêt de la fonction récursive ce fait lorsque la longueur L < 5
• La longueur maximale sera égale à 200
• A chaque récursion on réduit la longueur de 5
• Le module turtle qui permet de dessiner les lignes

Principales fonctions du module turtle

• goto(x,y)	Aller à l'endroit de coordonnées x et y
• forward(distance)	Avancer d'une distance donnée
• backward(distance)	Reculer
• up()	Relever le crayon (pour pouvoir avancer sans dessiner)
• down()	Abaisser le crayon (pour pouvoir recommencer à dessiner)
• color(couleur)	Couleur peut être une chaîne prédéfinie ('red', 'blue', 'green', etc.)
• left(angle)	Tourner à gauche d'un angle donné (exprimé en degré)
• right(angle)	Tourner à droite
• width(épaisseur)	Choisir l'épaisseur du tracé
• write(texte)	texte doit être une chaîne de caractères délimitée avec des " ou des '
• speed(vitesse)	Définit la vitesse de traçage (vitesse est un entier compris entre 0 à 9)

# Version itérative à transformer en récursive from turtle import * speed(0) i=5 while i<=200: forward(i) right(90) i+=5

Run

Résultat

Exercice 2 : ★★

l'arbre binaire

Cahier des charges

• Le tronc qui aura une longueur de 50 se fait avant la déclaration de la fonction.
• La condition d'arrêt se fait lorsque la longueur de la branche est inférieure à 5
• L'angle entre les branches est de 30° et la longueur de la première branche est égale à 100
• La longueur de la seconde branche et des branches suivantes seront divisées par 2

Pour résoudre le problème, on commence par dessiner uniquement 2 branches à partir du tronc :

Lorsqu'on atteint les extrémités des branches (en vert) on appelle récursivement la fonction avec L/2

from turtle import * up() goto(0,-100) down() left(90) forward(50) def arbre(L): if ??? :

Run

Résultat

Exercice 3 : ★★

Le flocon de Koch

Ordre 0	Ordre 1	ordre 2

Cahier des charges

• L'ordre 0 sera notre condition de sortie et est composée d'un segment de Longueur L
• L'ordre 1 est composé du motif d'ordre 0 de longueur L/3
• L'ordre 2 est composé du motif d'ordre 1 de Longueur L/3
• L'ordre 3 est composé du motif d'ordre 2 de Longueur L/3

Généralisation

A partir de l'ordre 1, l'ordre n est composé du motif de l'ordre n-1 de longueur L/3

Programmer le motif de l'ordre 0 lorsque n=0 sinon le motif d'ordre 1 appelant le motif d'ordre n-1 avec une longueur L/3

from turtle import* up() goto(-160,100) speed(0) down() n=2 L=340 def koch(n,L): if n==0: ??? else: ??? koch(n,L)

Run

Résultat

Exercice 4 : ★★

Le triangle de Sierpinzki

Ordre 0	Ordre 1	ordre 2

• L'ordre 0 sera notre condition de sortie et est composée d'un triangle de Longueur L
• L'ordre 1 est composé de 3 triangles d'ordre 0 de longueur L/2
• L'ordre 2 est composé de 3 triangles d'ordre 1 de Longueur L/2
• L'ordre 3 est composé de 3 triangles d'ordre 2 de Longueur L/2

Généralisation

A partir de l'ordre 1, l'ordre n est composé du motif de l'ordre n-1 de longueur L/2

Programmer le triangle d'ordre 0 de longueur L, puis les 3 triangles d'ordre 1, en appelant l'ordre n-1.

Le dessin des triangles commence en bas à gauche. Vous pouvez vous aider d'un crayon et d'une feuille de papier pour dessiner l'ordre 1

from turtle import * up() goto(-200,-180) down() def Triangle (n,L): if n == 0: for i in range (0,3): ??? else: ??? Triangle(2,400)

Run

Résultat

Fond : Texte : Tables :

Contenu sous licence CC BY-NC-SA 3.0
Pascal Hassenforder 21/11/2020
Mise à jour du 19/11/2021