recurs.cpp

int Fact(int n) { if(n == 1) return 1; else return (n*Fact(n-1)); }

Prenons comme exemple Fact(4) :

• Fact(4) renvoie 4*Fact(3)
• Fact(3) renvoie 3*Fact(2)
• Fact(2) renvoie 2*Fact(1)
• Fact(1) renvoie 1 (à cause du if)

Maintenant que la récursivité s'est arrêtée (c'était le dernier appel à la fonction Fact()), remontons la chaîne des valeurs de renvoi :

• Donc Fact(2) renvoie 2*Fact(1) = 2*1
• Donc Fact(3) renvoie 3*Fact(2) = 3*2*1
• Donc Fact(4) renvoie 4*Fact(3) = 4*3*2*1 = 24

Et hop, on obtient le même résultat. Et en gros, ça nous a pris deux lignes, et aucun calcul. N'est-ce pas une solution plus élégante que d'utiliser une boucle et 2 variables ?

Voyons tout de suite un autre exemple. Vous vous souvenez tous que pour savoir si un nombre est divisible par 3, il faut faire la somme de ses chiffres, et voir si celle-ci est divisible par 3 ? On remarque alors qu'on revient au point de départ : on se retrouve avec un second nombre dont on veut savoir s'il est divisible par 3. On fait donc la somme de ses chiffres à lui, etc, etc... jusqu'à ce qu'on trouve un chiffre, qui sera alors 3, 6 ou 9. Alors, on sait que le nombre de départ est divisible par 3. Sans le savoir, déjà à l'époque, on appliquait le principe de la récursivité. Faisons une application directe de ceci, en oubliant un instant que l'opérateur modulo peut nous dire si un nombre est divisible par un autre.

Il nous faut évidemment une fonction pour faire la somme des chiffres d'un nombre. Ce sera notre fonction récursive : elle calculera le résultat, et si ce résultat n'est pas un chiffre, elle renverra la somme des chiffres du résultat... et on aura une belle récursivité !

#include <iostream.h> int SommeChiffres(int n) { if(n == 0) return 0; // Pour ce cas particulier où n == 0 int total = 0; do { total += n%10; // Quel est le dernier chiffre? n /= 10; // Et on le supprime! } while(n != 0); if(total <= 9) return total; // C'est un chiffre! else return SommeChiffres(total); // C'est un nombre, on recommence } int main(void) { int n = 0; cout << "Entrez le nombre à tester : "; cin >> n; int resultat = SommeChiffres(n); if((resultat == 0) ||(resultat == 3) || (resultat == 6) || (resultat == 9)) cout << n << " est un multiple de 3!\n"; return 0; }

Cependant, faites attention : il faut une condition d'arrêt ! Sinon, la récursivité est infinie, et la fonction va se construire en mémoire jusqu'à ce qu'il n'y en ai plus, ce qui fera probablement planter votre programme (au bout d'un temps plutôt long). Dans le premier programme, la condition d'arrêt, c'est le if(n == 1). Dans le second, il s'agit de if(total <= 9).

La récursivité est relativement efficace en C++ car les appels de fonctions sont rapides. Cependant, si c'est l'une des techniques les plus élégantes de la programmation, ce n'est pas la plus efficace. Si vous recherchez la performance brute, utilisez plutôt une boucle.

Donc en gros :

Une fonction peut s'appeler elle-même. Dans une récursivité, il faut une condition d'arrêt.