Cet exemple illustre la programmation récursive.
La méthode récursive est une méthode "bourrin", - c'est vrai, - puisqu'elle va explorer toutes les possibilités jusqu'à trouver une solution, mais c'est parfois la seule méthode qui tienne la route, (rien n'empêche d'optimiser la recherche si c'est possible).
Mais sa principale qualité est qu'elle permet une programmation élégante, je dirais même limpide. Pour autant, les premières fois que l'on tente de la mettre en oeuvre, on peut se faire des noeuds à la tête !
Elle s'applique lorsque l'on est confronté à un problème que l'on ne sait pas résoudre, mais que l'on peut décomposer en problèmes élémentaires de même nature.
La solution du problème de complexité C est alors une fonction simple de la solution du problème de complexité C-1.
L'exemple bateau est le calcul de la fonction factorielle: Factorielle(e) = e x (e-1) x e(-2) x ... x 3 x 2 x 1,
(e étant un entier positif; si e est nul, Factorielle(e)=1).
Première solution: faire une boucle, (dans ce cas c'est la meilleure méthode).
Deuxième solution: l'algorithme récursif qui peut se programmer ainsi:
Private Function Factorielle(ByVal e As Long) As Long
If e <= 1 Then
Factorielle = 1
Else
Factorielle = e * Factorielle(e - 1)
End If
End Function
Remarques: e est supposé positif et pas trop grand pour éviter les overflow.
Il faudrait ajouter les contrôles d'erreur.
Quelques exemples de problèmes pouvant être résolus par récursivité:
- les tours de Hanoï;
- trouver le chemin pour qu'un cavalier parcourre toutes les cases d'un échiquier, une et une seule fois;
- placer huit reines sur un échiquier sans qu'elles ne se mettent en échec (voir l'exemple);
- recherche d'itinéraire.