T - 3.1 récursivité

Nous désirons créer un programme qui produise cette figure :

Pour cela nous allons utiliser le module turtle de façon très basique.

Vous devez commencer par vous connecter à votre compte replit pour faire les activités de dessin Turtle. Ensuite, vous cliquez sur le lien désiré, puis une fois le lien ouvert, en haut à droite, sur open in replit. Si ce n'est pas actif, bien penser à fermer toutes les boites de dialogues qui ont été ouvertes. Une fois la fenêtre de replit ouverte, il faudra cliquer en haut à droite sur Fork

Decouvrir Turtle : Si tu ne connais pas Turtle, ouvre le lien Découverte de Turtle en haut de la page pour apprendre les instructions de base dont nous aurons besoin.

Passons au dessin proprement dit

La récursivité en action : Utilise le lien Dessin récursif en haut de la page

Par exemple, nous voulons écrire un programme qui produit le dessin ci-dessous avec turtle. Cela semble assez difficile.

Le code utilisant une fonction récursive est finalement assez simple à imaginer .

Utiliser le lien Dessin récursif 2 en haut de la page pour voir sa structure

Nous voulons créer une fonction qui calcule aⁿ sans utiliser la fonction puissance.

Ci-dessous, la fonction puiss(a,n) qui renvoie la valeur de aⁿ. On a donc la transcription immédiate en Python :

Exemple

def puiss(a: int, n: int) -> int: ''' Cette fonction renvoie a**n sans utiliser ** ''' if n == 1 : return a else : return a*puiss(a, n - 1) # la fonction s'appelle elle-meme print(puiss(3, 4))

Regardons ce qu'il se passe si on appelle puiss(3,4)

De façon triviale puiss(3,1) renvoie 3.

La récursivité est une méthode de résolution de problèmes qui consiste à décomposer le problème en sous-problèmes identiques de plus en plus simples jusqu'à obtenir un problème suffisamment simple qui puisse être résolu de manière évidente (triviale).

On peut appeler ce problème très simple : cas de base, ou cas trivial.

Dans l'exemple précédant le cas de base est : puiss(a,1) qui renvoie a.

Pour le calcul de aⁿ , nous aurions pu tout simplement écrire le code suivant, qui est un code dit "itératif", sans utiliser une fonction récursive :

Exemple

def puiss_iter(a: int, n: int) -> int: ''' Cette fonction renvoie a**n sans utiliser ** ''' res = 1 for i in range(n): res = res * a return res print(puiss_iter(3, 4))

Le plus souvent nous utilisons une fonction récursive, lorsque cela est beaucoup plus simple à programmer qu'un programme itératif (décomposition en sous-problèmes identiques de plus en plus simples).

Attention ! Une fonction récursive étant une fonction qui s'appelle elle-même, on peut créer une fonction qui "tourne" indéfiniment.

Exemple

def puiss_fausse(a: int, n: int) -> int: ''' Cette fonction renvoie a**n sans utiliser ** ''' return a * puiss_fausse(a, n - 1) # la fonction s'appelle elle-meme puiss_fausse(3, 4)

Python s'arrête au bout d'un certain nombre d'appels récursifs, et affiche le message d'erreur. Il manquait dans cette fonction le cas de base :

if n == 1 :
       return a

Python limite explicitement le nombre d’appels récursifs dans une fonction. Ainsi, après 1000 appels récursifs, l’interpréteur Python va lever l’exception RecursionError et afficher le message d’erreur suivant : RecursionError: maximum recursion depth exceeded.

Cette limite, fixée à 1000 appels récursifs, est une valeur par défaut qu’il est possible de modifier en utilisant la fonction setrecursionlimit disponible dans le module sys. Par exemple, pour passer cette limite à 2000 appels maximum, on exécutera le code Python suivant :

       import sys
       sys.setrecursionlimit(2000)  

Un tel changement reste cependant dérisoire lorsque l’on a une définition récursive qui, par nature, effectue un très grand nombre d’appels emboîtés.

Source : spécialité Numérique et sciences informatiques, 24 leçons avec exercices corrigés classe de terminale - ellipses

Il peut y avoir un autre problème si les appels récursifs successifs éloignent du cas de base au lieu d'en rapprocher.

Reprenons la fonction puiss() écrite plus haut de façon récursive.

Exemple

def puiss(a: int, n: int) -> int: ''' Cette fonction renvoie a**n sans utiliser ** ''' if n == 1: return a else : return a*puiss(a, n - 1) # la fonction s'appelle elle-même print(puiss(4, -1))

Ici puiss(4, -1) appelle puiss(4, -2), qui appelle puis(4, -3) etc...

On n'atteindra jamais le cas de base qui aurait été puiss(4, 1), et le processus est infini.

1. Trouver le cas général : trouver l'élément de récursivité qui permet de décomposer le problème en cas plus simple.
2. Trouver le cas de base : trouver la condition d'arrêt, et la solution du problème dans ce cas particulier. La condition d'arrêt sera bien atteinte après un nombre fini d'appels. Chaque appel récursif tend à se rapprocher du cas de base.
3. Réunir ces deux cas dans le programme : Le programme ne contient aucune boucle (for ou while) dans la partie qui résout le problème. Le programme contient un général une structure if / else introduisant le cas de base

Alice a réalisé le code suivant pour savoir si un entier se trouve dans un tableau (typ list python). C'est une recherche par dichotomie utilisant une fonction récursive.

Exercice de code : Vous êtes Bob

Clique sur Visualiser pour debugguer ce code qui renvoi toujours None.

Vous devez créer un compte et vous connecter avant de poser une question.

def recherche(lst, x): ''' Cette fonction renvoie True si x est dans lst, et False sinon Précondition : x : int, lst : list et ... (à vous de compléter !) Postcondition : cette fonction renvoie du type booléen ''' if len(lst) == 0: return False m = len(lst) // 2 if lst[m] == x: return True elif lst[m] < x: recherche(lst[m + 1:], x) else: recherche(lst[:m], x) print(recherche([1, 2, 3, 4, 5, 6], 1)) print(recherche([1, 2, 3, 4, 5, 6], 6)) print(recherche([1, 2, 3, 4, 5, 6], 3)) print(recherche([1, 2, 3, 4, 5, 6], 8)) print(recherche([1, 2, 3, 4, 5, 6], 0))

Plus d'actions... Réinitialiser code Aide

Malheureusement, ce code ne fonctionne pas. Elle a donc demandé de l'aide à son ami Bob pour rectifier ce script. Vous êtes Bob, à vous de jouer !

Vous devez vous aider du bouton "visualiser" pour comprendre le déroulement du code proposé par Alice.

Compléter la fonction suivante, écrite de façon récursive, pour qu'elle retourne True si un entier est pair, et False sinon.
Vous ne pouvez pas utiliser le modulo %, ni la division /, ni la division entière //

Aide 1      Aide 2

Exercice de code : Parité

Clique sur Visualiser pour debugguer ce code qui renvoi toujours None.

Vous devez créer un compte et vous connecter avant de poser une question.

def est_pair(n: int) -> bool: ''' Cette fonction renvoie True si n est pair, False sinon Précondition: n est un entier positif ou nul Postcondition: la valeur retournée est de type booléen Exemple : >>> est_pair(4) True >>> est_pair(5) False >>> est_pair(0) True ''' assert n >= 0 ,'n est un entier positif ou nul' pass

Plus d'actions... Réinitialiser code Aide