Quand utiliser la récursivité?

Quand y a-t-il des cas (relativement) basiques (pensez aux étudiants CS de première année de niveau collégial) où l'on utiliserait la récursivité au lieu d'une simple boucle?

J'ai enseigné le C ++ aux étudiants de premier cycle pendant environ deux ans et couvert la récursivité. D'après mon expérience, votre question et vos sentiments sont très courants. À l'extrême, certains étudiants voient la récursivité comme difficile à comprendre tandis que d'autres veulent l'utiliser pour à peu près tout.

Je pense que Dave le résume bien: utilisez-le là où c'est approprié. Autrement dit, utilisez-le quand il semble naturel. Lorsque vous rencontrez un problème où il s'intègre bien, vous le reconnaîtrez très probablement: il semblera que vous ne pouvez même pas trouver de solution itérative. De plus, la clarté est un aspect important de la programmation. D'autres personnes (et vous aussi!) Devraient être capables de lire et de comprendre le code que vous produisez. Je pense qu'il est sûr de dire à première vue que les boucles itératives sont plus faciles à comprendre que la récursivité.

Je ne sais pas dans quelle mesure vous connaissez la programmation ou l'informatique en général, mais je pense fermement que cela n'a pas de sens de parler de fonctions virtuelles, d'héritage ou de concepts avancés ici. J'ai souvent commencé par l'exemple classique du calcul des nombres de Fibonacci. Cela convient parfaitement, car les nombres de Fibonacci sont définis de manière récursive . Ceci est facile à comprendre et ne nécessite aucune fonctionnalité sophistiquée de la langue. Une fois que les élèves ont acquis une compréhension de base de la récursivité, nous avons revu quelques fonctions simples que nous avons construites plus tôt. Voici un exemple:

Une chaîne contient-elle un caractère ?$x$

Voici comment nous l'avons fait auparavant: itérer la chaîne et voir si un index contient .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

La question est alors, pouvons- nous le faire récursivement? Bien sûr que nous pouvons, voici une façon:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

La prochaine question naturelle est alors, devons-nous le faire comme ça? Probablement pas. Pourquoi? C'est plus difficile à comprendre et plus difficile à trouver. Par conséquent, il est également plus sujet aux erreurs.

Les solutions à certains problèmes sont plus naturellement exprimées à l'aide de la récursivité.

Par exemple, supposons que vous ayez une structure de données arborescente avec deux types de nœuds: les feuilles, qui stockent une valeur entière; et les branches, qui ont un sous-arbre gauche et droit dans leurs champs. Supposons que les feuilles sont ordonnées, de sorte que la valeur la plus basse se trouve dans la feuille la plus à gauche.

Supposons que la tâche consiste à imprimer les valeurs de l'arborescence dans l'ordre. Un algorithme récursif pour ce faire est assez naturel:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Écrire du code équivalent sans récursivité serait beaucoup plus difficile. Essayez!

Plus généralement, la récursivité fonctionne bien pour les algorithmes sur les structures de données récursives comme les arbres, ou pour les problèmes qui peuvent naturellement être décomposés en sous-problèmes. Découvrez, par exemple, les algorithmes de division et de conquête .

Si vous voulez vraiment voir la récursivité dans son environnement le plus naturel, alors vous devriez regarder un langage de programmation fonctionnel comme Haskell. Dans un tel langage, il n'y a pas de construction en boucle, donc tout est exprimé à l'aide de la récursivité (ou des fonctions d'ordre supérieur, mais c'est une autre histoire, à savoir aussi).

Notez également que les langages de programmation fonctionnels effectuent une récursion de queue optimisée. Cela signifie qu'ils ne déposent pas de trame de pile sauf s'ils n'en ont pas besoin --- essentiellement, la récursivité peut être convertie en boucle. D'un point de vue pratique, vous pouvez écrire du code de manière naturelle, mais obtenir les performances du code itératif. Pour mémoire, il semble que les compilateurs C ++ optimisent également les appels de queue , il n'y a donc pas de surcharge supplémentaire d'utilisation de la récursivité en C ++.

De quelqu'un qui vit pratiquement en récursivité, je vais essayer de faire la lumière sur le sujet.

Lors de sa première introduction à la récursivité, vous apprenez qu'il s'agit d'une fonction qui s'appelle elle-même et qui est essentiellement illustrée par des algorithmes tels que la traversée d'arbre. Plus tard, vous constaterez qu'il est beaucoup utilisé dans la programmation fonctionnelle de langages tels que LISP et F #. Avec le F # que j'écris, la plupart de ce que j'écris est récursif et correspondance de motifs.

Si vous en savez plus sur la programmation fonctionnelle comme F #, vous apprendrez que les listes F # sont implémentées sous forme de listes liées individuellement, ce qui signifie que les opérations qui accèdent uniquement au début de la liste sont O (1) et que l'accès aux éléments est O (n). Une fois que vous avez appris cela, vous avez tendance à parcourir les données en tant que liste, en créant une nouvelle liste dans l'ordre inverse, puis en inversant la liste avant de revenir de la fonction qui est très efficace.

Maintenant, si vous commencez à y penser, vous vous rendez vite compte que les fonctions récursives pousseront un cadre de pile chaque fois qu'un appel de fonction est effectué et peut provoquer un débordement de pile. Cependant, si vous construisez votre fonction récursive afin qu'elle puisse effectuer un appel de fin et que le compilateur prenne en charge la possibilité d'optimiser le code pour l'appel de fin. c'est-à-dire .NET OpCodes.Tailcall Field vous ne causerez pas de débordement de pile. À ce stade, vous commencez à écrire toute boucle en tant que fonction récursive et toute décision en tant que correspondance; les jours ifet whilesont maintenant de l'histoire.

Une fois que vous passez à l'IA en utilisant le retour arrière dans des langues telles que PROLOG, tout est récursif. Bien que cela nécessite de penser d'une manière très différente du code impératif, si PROLOG est le bon outil pour le problème, il vous libère du fardeau d'avoir à écrire beaucoup de lignes de code et peut réduire considérablement le nombre d'erreurs. Voir: client Amzi eoTek

Pour revenir à votre question de savoir quand utiliser la récursivité; une façon dont je regarde la programmation est avec du matériel à une extrémité et des concepts abstraits à l'autre extrémité. Plus le problème est proche du matériel, plus je pense dans les langages impératifs ifet while, plus le problème est abstrait, plus je pense dans les langages de haut niveau avec récursivité. Cependant, si vous commencez à écrire du code système de bas niveau et autres, et que vous voulez vérifier qu'il est valide, vous trouverez alors des solutions comme les prouveurs de théorèmes utiles, qui reposent fortement sur la récursivité.

Si vous regardez Jane Street, vous verrez qu'ils utilisent le langage fonctionnel OCaml . Bien que je n'ai vu aucun de leur code, à la lecture de ce qu'ils mentionnent à propos de leur code, ils pensent sûrement récursivement.

MODIFIER

Puisque vous recherchez une liste d'utilisations, je vais vous donner une idée de base de ce qu'il faut rechercher dans le code et une liste des utilisations de base qui sont principalement basées sur le concept de catamorphisme qui est au-delà des bases.

Pour C ++: si vous définissez une structure ou une classe qui a un pointeur vers la même structure ou classe, la récursivité doit être prise en compte pour les méthodes de parcours qui utilisent les pointeurs.

Le cas simple est une liste chaînée à sens unique. Vous devez traiter la liste en commençant par la tête ou la queue, puis parcourir récursivement la liste à l'aide des pointeurs.

Un arbre est un autre cas où la récursivité est souvent utilisée; à tel point que si vous voyez une traversée d'arbre sans récursivité, vous devriez commencer à vous demander pourquoi? Ce n'est pas faux, mais quelque chose qui doit être noté dans les commentaires.

Les utilisations courantes de la récursivité sont:

• tri
• recherche
• carte
• plier
• filtre

Pour vous donner un cas d'utilisation qui est moins mystérieux que ceux donnés dans les autres réponses: la récursion se mélange très bien avec des structures de classe arborescentes (orientées objet) dérivant d'une source commune. Un exemple C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

L'exemple ci-dessus utilise la récursivité: ComputeValue est implémentée de manière récursive. Pour que l'exemple fonctionne, vous utilisez des fonctions virtuelles et l'héritage. Vous ne savez pas exactement ce que sont les parties gauche et droite de la classe Plus, mais peu vous importe: c'est quelque chose qui peut calculer sa propre valeur, c'est tout ce que vous devez savoir.

L'avantage crucial de l'approche ci-dessus est que chaque classe s'occupe de ses propres calculs . Vous séparez complètement les différentes implémentations de toutes les sous-expressions possibles: elles n'ont aucune connaissance du fonctionnement de l'autre. Cela facilite le raisonnement sur le programme et rend donc le programme plus facile à comprendre, à maintenir et à étendre.

Le premier exemple utilisé pour enseigner la récursivité dans ma classe de programmation débutante était une fonction pour lister tous les chiffres dans un nombre séparément dans l'ordre inverse.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Ou quelque chose comme ça (je vais de mémoire ici et je ne teste pas). De plus, lorsque vous entrez dans des classes de niveau supérieur, vous utiliserez beaucoup la récursivité en particulier dans les algorithmes de recherche, les algorithmes de tri, etc.

Donc, cela peut sembler être une fonction inutile dans le langage maintenant, mais c'est très très utile à long terme.