La récursivité est une méthode de résolution de problèmes basée sur la mentalité de diviser pour mieux régner. L'idée de base est que vous prenez le problème d'origine et que vous le divisez en instances plus petites (plus facilement résolues), résolvez ces instances plus petites (généralement en utilisant à nouveau le même algorithme), puis réassemblez-les dans la solution finale.

L'exemple canonique est une routine pour générer la factorielle de n. La factorielle de n est calculée en multipliant tous les nombres entre 1 et n. Une solution itérative en C

La récursivité fonctionne mieux avec ce que j'aime appeler des « problèmes fractals », où vous avez affaire à une grande chose qui est faite de versions plus petites de cette grande chose, chacune étant une version encore plus petite de la grande chose, et bientôt. Si jamais vous devez traverser ou rechercher dans quelque chose comme un arbre ou des structures identiques imbriquées, vous avez un problème qui pourrait être un bon candidat pour la récursivité.

Les gens évitent la récursivité pour plusieurs raisons :

1. La plupart des gens (moi y compris) ont fait leurs premières armes dans la programmation procédurale ou orientée objet, par opposition à la programmation fonctionnelle. Pour ces personnes, l'approche itérative (utilisant généralement des boucles) semble plus naturelle.

2. Ceux d'entre nous qui se sont fait les dents en programmation procédurale ou orientée objet se sont souvent fait dire d'éviter la récursivité, car elle est sujette aux erreurs.

3. On nous dit souvent que la récursivité est lente. Appeler et revenir d'une routine à plusieurs reprises implique beaucoup de poussées et de sauts de pile, ce qui est plus lent que la boucle. Je pense que certains langages gèrent cela mieux que d'autres, et ces langages ne sont probablement pas ceux où le paradigme dominant est procédural ou orienté objet.

4. Pour au moins quelques langages de programmation que j'ai utilisés, je me souviens avoir entendu des recommandations de ne pas utiliser la récursivité si elle dépasse une certaine profondeur, car sa pile n'est pas aussi profonde.

J'utilise la récursivité. Qu'est-ce que cela a à voir avec le fait d'avoir un diplôme d'informatique... (ce que je n'ai pas, soit dit en passant)

Utilisations courantes que j'ai trouvées :

1. sitemaps - parcourir le système de fichiers à partir de la racine du document
2. spiders - exploration d'un site Web pour trouver une adresse e-mail, des liens, etc.
3.  ?

Mario, je ne comprends pas pourquoi vous avez utilisé la récursivité pour cet exemple. Pourquoi ne pas simplement parcourir chaque entrée ? Quelque chose comme ça :

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

La méthode ci-dessus serait plus rapide et plus simple. Il n'est pas nécessaire d'utiliser la récursivité à la place d'une simple boucle. Je pense que ce genre d'exemples est la raison pour laquelle la récursivité a mauvaise presse. Même l'exemple de la fonction factorielle canonique est mieux implémenté avec une boucle.

Pour récurrencer sur un problème résolu : ne faites rien, vous avez terminé.
Pour récurrencer sur un problème ouvert : effectuez l'étape suivante, puis récurrez sur le reste.