TD n°10 Fonctions récursives

- Suite de la programmation en Python

- Utilisation de la récursivité pour le tracé d’une fractale dans le module turtle.

Savoirs Capacités

Fonctions

-notion de fonction

-portée des variables

-définition récursive de fonctions

Concevoir l’entête d’une fonction, puis la

fonction elle-même.

I – NOTION DE FONCTION ET

EXEMPLE - Rappels Une fonction est un morceau de programme autonome qui

réalise une tâche précise et bien définie. Le but de la fonction est : • de structurer le code : on obtient un code plus lisible, il est

inutile de savoir comment la fonction est écrite, il suffit de savoir ce qu'elle produit pour comprendre le programme principal.

• d’isoler une instruction qui revient plusieurs fois dans un programme : on obtient ainsi des programmes plus courts et plus lisibles.

• d’organiser plus aisément le travail de développement : on peut confier à une personne l'écriture d'une ou plusieurs fonctions, et l'écriture du programme principal à une autre.

La règle de base à respecter : le code d’une fonction ne doit pas dépasser une page de programme. Une fonction est définie par • un nom (choisir un nom qui indique clairement ce

que fait la fonction) • ses arguments qui porteront les valeurs

communiquées par le programme principal à la fonction au moment de son appel

• éventuellement une valeur de retour communiquée au programme par la fonction en fin d’exécution.

Principe général : l’entête de la fonction indique

son mode d’emploi.

En Python, pour définir une fonction, on utilise le mot-clé def, dont voici la syntaxe : (ce qui est entre [ ] est optionnel).

Exemple:

Quel est le résultat renvoyé par cette fonction ?

Quel doit être le type des arguments de cette fonction ?

II – PARAMETRES D’UNE FONCTION et

PORTEE DE VARIABLES 1) Paramètres d’une fonction

• Il peut y avoir plusieurs paramètres à une fonction et ce nombre doit être fixé au moment où on définit la fonction.

• Pour pouvoir appeler une fonction il faut donc connaître les informations concernant les paramètres :

leur nombre, leurs types, et à quoi ils correspondent.

Pour pouvoir l'utiliser il faut également savoir à quoi correspond son résultat et quel traitement est réalisé. Toutes ces informations doivent être décrites dans la spécification de la fonction.

Exemple 1:

Quel est le rôle de cette fonction ?

Exemple 2 :

Quelle est la différence avec la fonction précédente ?

Exemple 3 :

Que fait cette nouvelle fonction ?

2) Portée de variables :

variables globales et locales

La portée d’une variable est l’endroit du programme où on peut accéder à la variable.

Tester ce programme. Quel est l’affichage obtenu ?

Quel est le nouvel affichage ?

Conclusion : • La variable a de valeur 20 est créée dans la fonction du 1er

exemple : c’est une variable locale à la fonction. Elle est détruite dès que l’on sort de la fonction. Les variables utilisées dans une fonction sont locales et n’ont pas d’incidences sur le programme principal, sauf s’il a été mentionné dans le corps de la fonction qu’une variable est globale à l’aide de l’instruction global. • Dans le 2ème exemple, a=20 après l’appel de la fonction. • Il est préférable d’éviter l’utilisation global car c’est une

source d’erreurs (on peut modifier le contenu d’une variable sans s’en rendre compte, surtout dans les gros programmes).

III – FONCTIONS RECURSIVES

• Une fonction qui s’exécute en s’appelant elle-même est dite récursive.

• La récursivité est donc une méthode de programmation qui permet de simplifier certaines fonctions.

Exemple : FACTORIEL

• Rappel : La fonction factorielle n, qui se note en mathématiques n! a pour valeur :

n! = 1×2×3×…×n

Ex : 4!=1x2x3x4=24

Pour programmer cette fonction, on peut :

• soit utiliser une boucle

• Soit créer un algorithme récursif

Avec une boucle :

Soit l’algorithme suivant qui n’est pas récursif :

Fonction factorielle (n entier)

– Résultat=1

– Pour i allant de 1 à n

– Résultat = x*i

– Finpour factorielle (n entier)

Retourner le résultat

Avec un algorithme récursif :

Fonction factorecu (n : entier)

• Si n == 0

• Alors retourner 1 # Cette première instruction est nécessaire pour que la fonction s’arrête et est appelée condition d’arrêt

• Sinon retourner n×factorecu (n-1) # appel de la fonction factorecu, l’argument est décrémenté d’une unité et finira par être égal à 0, ce qui garantit que le programme s’achèvera.

• Finsi

Correction Programmation de n! avec la boucle :

Correction Programmation de n! Méthode récursive

IV – Application aux fractales avec le

module turtle La notion de récursivité peut être illustrée

géométriquement par des fractales. Présentation de fonctions graphiques de Python. • Nous allons utiliser la bibliothèque turtle de

Python assimilable à un ensemble de points d’un plan.

• Chaque point est désigné par deux coordonnées entières sur le plan.

• L’origine (coordonnées (0 , 0)) est située au centre de la fenêtre. La taille de la fenêtre par défaut est de (400 , 300).

Voici quelques fonctions de base de turtle Python :

• Pendown( ) : met le crayon en position basse permet de tracer. • Penup( ) : permet de lever le crayon en vue de déplacement sans

tracer. • Goto(x,y) : sert à déplacer le curseur vers un point dont on précise

les coordonnées. • Forward(x) : permet de tracer un segment de longueur x (en pixels) • speed() change la vitesse à laquelle la tortue se déplace. Cette

instruction prend une valeur entre 1 et 11. 11 est le plus rapide, 1 le plus lent.

• shape() change la forme de la tortue. Nous utilisons la forme “turtle” pour dessiner une tortue, mais nous pourrions aussi utiliser les valeurs “arrow” (flèche), “circle” (cercle), “square” (carré), “triangle” (triangle) or “classic” (classique).

Exercice 1

▶penup() ▶ right(90)

▶pendown() ▶ backward(100)

▶ goto(100,100) ▶left(120)

▶ forward(50) ▶goto(-100,-100)

▶from turtle import *

Puis tester les commandes suivantes en déduisant les fonctionnalités de ces commandes.

Dans le Shell de Python faites appel à la librairie turtle :

Exercice 2

• Compléter la fonction suivante permettant de

tracer un carré de côté x en partant du milieu de la fenêtre :

Exercice 3

Tester ce programme et le modifier pour obtenir un autre graphisme :

Courbes fractales

avec une fonction récursive • La courbe de Koch est l'une des premières

courbes fractales à avoir été décrite.

• Elle a été inventée en 1904 par le mathématicien suédois Helge von Koch.

Voici les premières étapes de sa construction :

• On part du dessin B), figure de base, qui va se reproduire elle-même sur chacune des branches. • Cette figure de base est constituée de quatre branche de longueur a. • On peut donc considérer que la figure C) est constituée ainsi : ▪ une figure de base de côté a/3 ▪ une rotation à gauche de 60° ▪ une figure de base de côté a/3 ▪ une rotation à droite de 120° ▪ une figure de base de côté a/3 ▪ une rotation à gauche de 60° ▪ une figure de base de côté a/3

On appelle ainsi les figures de base les unes dans les autres de façon récursive jusqu’à ce que a/3 ait atteint une limite que l’on s’est fixée (par exemple de 10 comme dans l’exemple ci-dessous).

Lors de l’appel de la fonction courbekoch, les instructions s’empilent les unes sur les autres sans rien faire d’autre et ne commence à tracer que lorsque le paramètre (a < 10) est vérifié.

Exercice 4

• Tester le programme précédent.

• Faire des essais en faisant varier la condition (a > 10)

• En imaginant que le flocon complet n’est autre que trois courbes de Van Koch comme celle que l’on vient de réaliser au-dessus, écrire le programme permettant d’obtenir le flocon en entier.

Fin de la séance ….

Merci !