introduction

La notion de récursivité est une notion essentielle, et pas seulement en informatique. En effet, pour expliquer une situation, on utilise souvent cette même situation à un état précédent.

La récursivité

La récursivité

Une des premières choses que l'on apprend lorsqu'on commence à programmer est la notion de boucle : on a souvent besoin dans un algorithme de répéter une partie du programme.

Observons l'algorithme d'Euclide par exemple pour trouver le PGCD de deux entiers : Vous avez probablement utilisé une boucle Tant que pour implémenter cet algorithme. En voici une version simple :

def pgcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

Mais si on prend soin d'observer la manière de définir l'algorithme d'Euclide :

Si a est divisible par b, le pgcd de a et b vaut b
sinon le pgcd de a et b vaut le pgcd de b et a%b

cet algorithme s'arrête car a%b est un entier naturel strictement inférieur à b donc à un moment donné ce reste sera nul c'est à dire a est divisible par b. Vous voyez que la manière la plus simple et naturelle d'énoncer cet algorithme est de définir le pgcd par le pgcd lui même !

Notion de récursivité

Lorsque la définition d'un objet fait appel à l'objet lui même, on parle de définition récursive. On rencontre souvent cette notion de récursivité :

Dans la vie de tous les jours :

Sur les boites de vache-qui-rit

Dans la nature

Définition générale

On dit qu’on définit une notion nouvelle de manière récursive lorsque cette notion fait partie de sa propre définition.

Cette manière de procéder heurte le sens commun car on a l’habitude de définir un objet en utilisant des objets connus, mais c’est pourtant le mode de pensée le plus adapté à beaucoup de problèmes.

D’une manière générale, une définition récursive doit être complétée par la connaissance d’un cas particulier au moins (le point d’appui) pour lequel on connaît explicitement le résultat, souvent trivial.

En informatique

Vous l'avez compris, la récursivité est partout, et donc bien sûr en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Dans LISP, elle est tellement fondamentale que ce langage ne possède pas de structures de boucles ! tout se fait avec la récursivité !

Tous les langages de programmation haut niveau peuvent utiliser la récursivité, c'est à dire la faculté que possède une fonction à s'appeler elle-même.

Premier exemple

Revenons sur notre exemple de l'algorithme d'Euclide. Une autre manière de l'implémenter est de traduire en python mot à mot la manière dont on a décrit cet algorithme. Pour rappel :

Si a est divisible par b, le pgcd de a et b vaut b
sinon le pgcd de a et b vaut le pgcd de b et a%b

ce qui donne en une seule ligne de python !!

def pgcd(a, b):
    return b if a%b == 0 else pgcd(b, a%b)

Remarquez à quel point la syntaxe Python est proche du langage naturel ! On peut écrire cette fonction de manière plus explicite, ce n'est guerre plus compliqué :

def pgcd(a, b):
    if a%b == 0:
        return b
    else:
        return pgcd(b, a%b) 

Une fonction récursive se caractérise par deux propriétés :

• une condition, d'arrêt
• la fonction contient un (ou plusieurs) appel(s) à elle-même à l'intérieur de celle-ci

La programmation récursive s'avère extrêmement pratique lorsque la résolution d'un problème se ramène à celle d'un problème plus petit. A force de réduire notre problème, on arrive à un problème trivial que l'on sait résoudre : c'est ce qu'on utilise dans notre condition d'arrêt.

A présent vous êtes prêt à réaliser les activités à déposer.

Commencer dans l'ordre que vous souhaitez.