NSI Terminale
-->

Recursivité


Contenus : Récursivité.

Capacités attendues : Écrire un programme récursif. Analyser le fonctionnement d’un programme récursif.

Commentaires : Des exemples relevant de domaines variés sont à privilégier.

Logiciel nécessaire pour l'activité : Python 3 : Spyder, IDLE ...

Prérequis : les activités suivantes

  • Programmation : programmation itérative - boucles,

A RENDRE ✎ :

1 - Définition

  • Larousse :

    • récursivité :

      Propriété que possède une règle ou un élément constituant de pouvoir se répéter de manière théoriquement indéfinie. (C’est une propriété essentielle des règles d’une grammaire générative, celle qui permet d’engendrer un nombre infini de phrases.)

      Qualité d’un programme informatique récursif.

      Théorie destinée à fournir un cadre rigoureux à l'étude des notions intuitives de calculabilité et de décidabilité effectives. (Church a montré [1936] que la récursivité est l'équivalent mathématique de la calculabilité effective : la fonction récursive est une fonction rigoureusement calculable.)

    • récursif :

      Se dit d’une règle ou d’un élément doués de récursivité. Se dit d’un programme informatique organisé de manière telle qu’il puisse se rappeler lui-même, c’est-à-dire demander sa propre exécution au cours de son déroulement.

    Avec au passage, un bel exemple de récursivité (croisée).

  • Wikipédia :

    La récursivité est une démarche qui fait référence à l’objet même de la démarche à un moment du processus. En d’autres termes, c’est une démarche dont la description mène à la répétition d’une même règle. Ainsi, les cas suivants constituent des cas concrets de récursivité :

    • décrire un processus dépendant de données en faisant appel à ce même processus sur d’autres données plus « simples » ;
    • montrer une image contenant des images similaires ;
    • définir un concept en invoquant le même concept ;
    • écrire un algorithme qui s’invoque lui-même ;
    • définir une structure à partir de l’une au moins de ses sous-structures.

2 - Exemples

processus récursif

  1. Calcul de la fonction dérivée d’une fonction dérivable

Entrée : f (une fonction dérivable) - Sortie : f’ (la fonction dérivée)

derivee(f) =
    si f est une fonction élémentaire de base
        renvoyer sa dérivée
    sinon si f == u+v
        renvoyer derivee(u) + derivee(v)
    sinon si f == u × v
        renvoyer derivee(u)×v + u×derivee(v)
    sinon si …
  1. Production de fractales : le flocon de Von Koch

On dispose de la primitive tracer(l) qui permet de tracer un segment de longueur l.

Le processus de tracé d’un segment de von koch de taille l à l’ordre n est :

vonkoch(l,n)

  • si n = 1, tracer(l)

  • sinon

    • vonkoch(l/3, n-1)
    • tourner à gauche de 60°
    • vonkoch(l/3, n-1)
    • tourner à droite de 120°
    • vonkoch(l/3, n-1)
    • tourner à gauche de 60°
    • vonkoch(l/3, n-1)

Le flocon est obtenu en traçant 3 segments de von koch séparés par des rotations à droite de 120°.

flocon von koch

NB Se réalise très bien avec la tortue (module turtle), tracer(l) = forward(l) et les fonctions rightet left permettent les rotations

Images

Sigles

C'est sigles sont auto-référentiels, ils font appel à la récursivité et plus précisément à l'auto-référence

  • VISA : VISA International Service Association
  • GNU : GNU is Not Unix
  • WINE : Wine Is Not an Emulator
  • Bing : Bing is not Google (non officiel)
  • LAME : Lame Ain’t an MP3 Encoder

Grammaire

Un groupe nominal est composé d’un nom ou d’un nom et son complément. Le complément d’un nom est soit un adjectif, soit un adverbe, soit un groupe nominal. (très approximativement)

groupe_nominal ::=    nom
                    | nom complement
complement     ::=    adjectif
                    | adverbe
                    | groupe_nominal

Algorithme récursif

Le tri rapide

Structures récursives

listes, arbres

3 - Fonctionnement par un exemple

En classe de première, de nombreux programmes sont écrits avec des boucles et des affectations.

La notion de fonction permet en particulier d'éviter de réécrireun code similaireà plusieurs endroits d'un programme.

Le style de programmation est :

  • impétatif, les séquences d'instructionssonr exécutées l'une après l'autre;
  • itératif, des instructions sont exécutéesdans des boucles while ou for

Différents styles de programmations seront présentés dans un prochain chapitre.

Définitions

    Fonction récursive
    • Une fonction est dite récursive si elle s'appelle elle même.
    • Nous parlons alors d'appel récursif.

    • De manière générale, un sous programme est dit récursif s'il s'appelle lui même.

Exemple : la somme des n premiers entiers

  • Pour définir la somme des n premiers entiers, on a l’habitude d’écrire la formule suivante :
    • 0 + 1 + 2 + ... + n

01° Ecrire, en Python, une fonction somme(n) qui calcule la somme des n premiers entiers naturels.

  1. En utilisant une boucle for
  2. En utilisant une boucle while
  • Autre méthode

      Il existe en effet une autre manière d’aborder ce problème. Il s’agit de définir une fonction mathématique somme(n) qui, pour tout entier naturel n, donne la somme des n premiers entiers de la manière suivante :

        somme

      Cette définition nous indique ce que vaut somme(n) pour un entier n quelconque,selon que n soit égal à 0 ou strictement positif.

      Ainsi, pour n = 0,la valeur de somme(0) est simplement 0.
      Dans le cas où n est strictement positif, la valeur de somme(n) est n + somme(n − 1).

        Par exemple

      voici ci-dessous les valeurs de somme(n), pour n valant 0, 1, 2 et 3.

        somme0

      Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n − 1).
      Il s’agit là d’une définition récursive, c’est-à-dire d’une définition de fonction qui fait appel à elle-même.
      Ainsi, pour connaître la valeur de somme(n), il faut connaître la valeur de somme(n − 1), donc connaître la valeur de somme(n−2), etc.
      Ceci jusqu’à la valeur de somme(0) qui ne dépend de rien et vaut 0.

      La valeur de somme(n) s’obtient en ajoutant toutes ces valeurs.


  • Principe de la recursivité
    • L’intérêt de cette définition récursive de la fonction somme(n) est qu’elle est directement calculable, c’est-à-dire exécutable par un ordinateur.
      En particulier, cette définition est directement programmable en Python, comme le montre le code ci-dessous:

      def somme(n):
          if n == 0:
              return 0
          else:
              return n + somme(n-1)
      

      L’analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle pour tester si l’argument n est égal à 0.
      Si c’est le cas, la fonction renvoie la valeur 0, sinon elle renvoie la somme n + somme(n - 1).

      Cet appel à somme(n - 1) dans le corps de la fonction est un appel récursif , c’est-à-dire un appel qui fait référence à la fonction que l’on est en train de définir.

      On dit de toute fonction qui contient un appel récursif que c’est une fonction récursive.

        Exemple pour n = 3

        l’évaluation de l’appel à somme(3) peut se représenter de la manière suivante

          somme0

        où on indique uniquement pour chaque appel à somme(n) l’instruction qui est exécutée après le test n == 0 de la conditionnelle.
        Cette manière de représenter l’exécution d’un programme en indiquant les différents appels effectués est appelée arbre d’appels.


        Ainsi, pour calculer la valeur renvoyée par somme(3), il faut tout d’abordappeler somme(2).
        Cet appel va lui-même déclencher un appel à somme(1),qui à son tour nécessite un appel à somme(0).
        Ce dernier appel se termine directement en renvoyant la valeur0.

        Le calcul de somme(3) se fait donc « à rebours ».
        Une fois que l’appel à somme(0) est terminé, c’est-à-dire que la valeur 0 a été renvoyée,
        l’arbre d’appels a la forme suivante, où l’appel à somme(0) a été remplacé par 0 dans l’expression return 1 + somme(0).

          somme0

        À cet instant, l’appel à somme(1) peut alors se terminer et renvoyer le résultat de la somme 1 + 0.
        L’arbre d’appels est alors le suivant.

          somme0

        Enfin, l’appel à somme(2) peut lui-même renvoyer la valeur 2 + 1 comme résultat,
        ce qui permet à somme(3) de se terminer en renvoyant le résultat de 3 + 3.

          somme4

        On obtient bien au final la valeur 6 attendue

    Eléments Caractéristiques

      1. il faut au moins une situation qui ne consiste pas en un appel récursif.
      2.                 
                        if n == 0:
                            return 0
                        
                    

        Cette situation est appelée situation de terminaison ou situation d’arrêt ou cas d’arrêt ou cas de base.

      3. chaque appel récursif doit se faire avec des données qui permettent de se rapprocher d’une situation de terminaison.
      4.                 
                        return n + somme(n-1)
                        
                    

        Il faut s’assurer que la situation de terminaison est atteinte après un nombre fini d’appels récursifs.

4 - Aures Exemples

Exemple 1 : La fonction Factorielle

la fonction factorielle est définie, pour tout entier naturel n par (noté : n!) :

  • 0! = 1
  • n! = n x (n-1)! si n > 1
  • Principe :

      5! = 5 x 4!
         = 5 x 4 x 3!
         = 5 x 4 x 3 x 2!
         = 5 x 4 x 3 x 2 x 1!
         = 5 x 4 x 3 x 2 x 1 x 0!
         = 5 x 4 x 3 x 2 x 1 x 1
         = 120
    

    Programmation

    def fact(n):
        if n <= 1:
            return 1
        else:
            return n * fact(n-1)
    
    >>> fact(5)
    120
    

    Déroulement de l’exécution

    Mise en évidence :


Exemple 2 : Calculer le nombre d’occurrences d’un caractère dans une chaîne

Il faut trouver un énoncé récursif de résolution du problème, c’est-à-dire un énoncé qui fasse référence au problème lui-même

    Énonce

    s la chaine de caractères et c est le caractère cherché.
    • Le nombre d’occurrences de c dans s est 0 si s est vide.
    • Si c est le premier caractère de s, on ajoute 1 au nombre d’occurrences de c dans les autres caractères de s.
    • Sinon, il s’agit du nombre d’occurrences de c dans les autres caractères de s.

    Programmation

    def occurrences(c,s):
        if s == "":
           return 0
        elif c == s[0]:
        	 return 1 + occurrences(c,s[1:])
        else:
             return occurrences(c,s[1:])
    

    La terminaison se vérifie en considérant la suite des longueurs des chaînes passées en paramètre.

    Déroulement de l’exécution

    Mise en évidence :

5 - Récursivité Terminale

Définition

    Un algorithme récursif simple est terminal lorsque l’appel récursif est le dernier calcul effectué pour obtenir le résultat.

    Il n’y a pas de “calcul en attente”.

    L’avantage est qu’il n’y a rien à mémoriser dans la pile.

Ce n’est pas le cas des deux exemples précédents fact et occurrences.


Exemple d’algorithme récursif terminal

    Prédicat de présence d’un caractère dans une chaîne

    • Un caractère c est présent dans une chaîne s non vide, s’il est le premier caractère de s ou s’il est présent dans les autres caractères de s.
    • Il n’est pas présent dans la chaîne vide.

    Programmation

    def est_present(c,s):
        if s == '':
            return False
        elif c == s[0]:
            return True
        else:
            return est_present(c,s[1:])
        

    Déroulement de l’exécution

    Mise en évidence :


Rendre terminal un algorithme récursif

    Méthode

    On utilise un accumulateur, passé en paramètre, pour calculer le résultat au fur et à mesure des appels récursifs.

    La valeur de retour du cas de base devient la valeur initiale de l’accumulateur et lors d’un appel récursif, le “calcul en attente” sert à calculer la valeur suivante de l’accumulateur.

    Ainsi on obtient :

    def fact_term(n, acc = 1):
        if n <= 1:
            return acc
        else:
            return fact_term(n-1, acc * n)
    

    et

    def occurrences_term(c,s, acc = 0):
        if s == "":
           return acc
        elif c == s[0]:
             return occurrences_term(c,s[1:], acc + 1)
        else:
             return occurrences_term(c,s[1:], acc)
    
             

Activité publiée le 20 08 2020
Dernière modification : 27 08 2020
Auteur : Andjekel