C1 Recursivité - Cours

Définitions

• 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.

• 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.

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 …

2. 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°.

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

• Print gallery M.C.Escher (mise en abime)
• La vache qui rit (mise en abime)
• Pochette Ummagumma de Pink Floyd

Défintions et caractéristiques informatiques

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éécrire un code similaireà plusieurs endroits d'un programme.

Le style de programmation est :

• impératif, 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

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.

Eléments Caractéristiques

1. il faut au moins une situation qui ne consiste pas en un appel récursif.

                
                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.

2. chaque appel récursif doit se faire avec des données qui permettent de se rapprocher d’une situation de terminaison.

                
                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.

Synthèse de cours

Vous pouvez télécharger une copie au format pdf du diaporama de synthèse de cours présenté en classe :

Diaporama de cours

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.