Algorithmes récursifs

Un algorithme récursif est une méthode où un problème est résolu en faisant référence à une version plus petite de lui-même. L’idée correspond aux définitions récursives en mathématiques : on commence par une base, puis suit un pas récursif, qui répète l’algorithme sur une partie plus simple du problème.

 

 

De la définition au code

Lorsqu’on dispose d’une définition récursive, elle peut souvent être traduite directement en algorithme. Il suffit de traduire :

 

• Base : quand l’algorithme peut s’arrêter.
• Pas récursif : comment le problème est réduit et l’algorithme s’appelle lui-même.

 

 

Exemple : Factorielle

La fonction factorielle est définie récursivement comme

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

Cela peut s’écrire comme un algorithme en pseudocode :

 

function factorial(n):
    if n = 0:
        return 1        // base
    else:
        return n * factorial(n - 1)   // pas récursif

 

 

L’algorithme s’arrête lorsque \( \large n = 0 \); sinon, il s’appelle lui-même avec un nombre plus petit. Enfin, tous les appels se replient sur le résultat.

 

 

Exemple : Maximum dans une liste

On peut également définir un algorithme récursif pour trouver le plus grand nombre dans une liste :

 

• Base : Si la liste n’a qu’un seul élément, cet élément est le maximum.
• Pas récursif : Comparer le premier élément avec le maximum du reste de la liste.

 

 

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // pas récursif
        return the larger of list[0] and m

 

 

Exemple pratique

 

Si nous avons la liste \( \large [7, 2, 9, 4] \):

max([7,2,9,4])

= plus grand de 7 et max([2,9,4])

= plus grand de 7 et plus grand de 2 et max([9,4])

= plus grand de 7 et plus grand de 2 et plus grand de 9 et max([4])

= plus grand de 7 et plus grand de 2 et plus grand de 9 et 4

= plus grand de 7 et plus grand de 2 et 9

= plus grand de 7 et 9

= 9

 

 

Résumé

Un algorithme récursif traduit l’idée derrière une définition récursive en code. On indique d’abord un cas de base où l’algorithme s’arrête. Ensuite, on décrit un pas récursif, où l’algorithme s’appelle lui-même sur un problème plus simple. Ce schéma se retrouve dans de nombreux algorithmes connus, comme le tri, la recherche et le traitement des structures de données.