Quelles sont les considérations pour déterminer si vous pouvez utiliser la récursivité pour résoudre un problème?

Parfois, dans les entretiens, je peux utiliser la récursivité pour résoudre un problème (comme ajouter 1à un entier de précision infinie), ou lorsque le problème se présente comme approprié pour utiliser la récursivité. Parfois, cela peut simplement être dû à l'utilisation fréquente de la récursivité pour la résolution de problèmes, donc sans trop réfléchir, la récursion est utilisée pour résoudre le problème.

Cependant, quelles sont les considérations avant de pouvoir décider qu'il est approprié d'utiliser la récursivité pour résoudre un problème?

Quelques réflexions que j'ai eues:

Si nous utilisons la récursivité sur des données qui sont divisées par deux à chaque fois, il semble que l'utilisation de la récursion ne pose aucun problème, car toutes les données pouvant tenir dans 16 Go de RAM, ou même un disque dur de 8 To, peuvent être traitées par récursivité à seulement 42 niveaux de profondeur. (donc pas de débordement de pile (je pense que dans certains environnements, la pile peut avoir une profondeur de 4000 niveaux, bien plus que 42, mais en même temps, cela dépend aussi du nombre de variables locales dont vous disposez, car chaque pile d'appels occupe plus de mémoire) s'il existe de nombreuses variables locales, et c'est la taille de la mémoire, et non le niveau, qui détermine le débordement de la pile)).

Si vous calculez les nombres de Fibonacci en utilisant la récursivité pure, vous devez vraiment vous soucier de la complexité temporelle, sauf si vous mettez en cache les résultats intermédiaires.

Et que diriez-vous d'ajouter 1à un entier de précision infinie? Peut-être que cela peut être discuté, car travaillerez-vous avec des nombres de 3 000 chiffres ou de 4 000 chiffres, si gros que cela peut provoquer un débordement de pile? Je n'y ai pas pensé, mais peut-être que la réponse est non, nous ne devrions pas utiliser la récursivité, mais simplement utiliser une boucle simple, car si dans certaines applications, le nombre doit vraiment être de 4000 chiffres, pour vérifier certains propriétés du nombre, par exemple si le nombre est premier ou non.

La question ultime est: quelles sont les considérations avant de pouvoir décider d'utiliser la récursivité pour résoudre un problème?

Une considération est de savoir si votre algorithme est destiné à être une solution abstraite ou une solution exécutable pratique. Dans le premier cas, les attributs que vous recherchez sont la justesse et la facilité de compréhension pour votre public cible ¹ . Dans ce dernier cas, les performances sont également un problème. Ces considérations peuvent influencer votre choix.

Une deuxième considération (pour une solution pratique) est de savoir si le langage de programmation (ou plus strictement, sa mise en œuvre) que vous utilisez fait l'élimination des appels de queue? Sans élimination de l'appel de queue, la récursivité est plus lente que l'itération et une récursivité profonde peut entraîner des problèmes de dépassement de pile.

Notez qu'une solution récursive (correcte) peut être transformée en une solution non récursive équivalente, vous n'avez donc pas nécessairement besoin de faire un choix difficile entre les deux approches.

Enfin, parfois, le choix entre des formulations récursives et non récursives est motivé par la nécessité de prouver (au sens formel) les propriétés d'un algorithme. Les formulations récursives permettent plus directement la preuve par induction.

^{1 - Cela inclut des considérations comme si le public cible ... et cela pourrait inclure des programmeurs lisant du code pratique ... considéreraient un style de solution comme "plus naturel" que l'autre. La notion de «naturel» variera d'une personne à l'autre, selon la façon dont ils ont appris la programmation ou l'algorithmique. (Je mets au défi quiconque propose la «naturalité» comme critère principal pour décider d'utiliser (ou non) la récursivité pour définir la «naturalité» en termes objectifs, c'est-à-dire comment la mesureriez-vous.)}

En tant que programmeur C / C ++, ma principale considération est la performance. Mon processus de décision est quelque chose comme:

1. Quelle est la profondeur maximale de la pile d'appels? Si elle est trop profonde, débarrassez-vous de la récursivité. S'il est peu profond, passez à 2.

2. Cette fonction est-elle susceptible d'être un goulot d'étranglement de mon programme? Si oui, passez à 3. Sinon, conservez la récursivité. En cas de doute, exécutez un profileur.

3. Quelle est la fraction du temps processeur consacré aux appels de fonction récursifs? Si les appels de fonction prennent beaucoup moins de temps que le reste du corps de la fonction, il est correct d'utiliser la récursivité.

Cependant, quelles sont les considérations avant de pouvoir décider qu'il est approprié d'utiliser la récursivité pour résoudre un problème?

Lors de l'écriture de fonctions dans Scheme, je trouve naturel d'écrire des fonctions récursives de queue sans trop réfléchir.

Lors de l'écriture de fonctions en C ++, je me retrouve à débattre avant d'utiliser une fonction récursive. Les questions que je me pose sont:

• Le calcul peut-il être effectué à l'aide d'un algorithme itératif? Si oui, utilisez une approche itérative.

• La profondeur de récursivité peut-elle augmenter selon la taille du modèle? J'ai récemment rencontré un cas où la profondeur de récursivité est passée à près de 13 000 en raison de la taille du modèle. J'ai dû convertir la fonction pour utiliser un algorithme itératif après la hâte.

  Pour cette raison, je ne recommanderais pas d'écrire un algorithme de traversée d'arbre à l'aide de fonctions récursives. Vous ne savez jamais quand l'arborescence devient trop profonde pour votre environnement d'exécution.

• La fonction peut-elle devenir trop alambiquée en utilisant un algorithme itératif? Si oui, utilisez une fonction récursive. Je n'ai pas essayé d'écrire en qsortutilisant une approche itérative mais j'ai le sentiment que l'utilisation d'une fonction récursive lui est plus naturelle.

Pour les nombres de Fibonacci, la "récursivité" naïve est tout simplement stupide. En effet, cela conduit à résoudre le même sous-problème à maintes reprises.

Il existe en fait une variation triviale des nombres de Fibonacci où la récursivité est très efficace: étant donné un nombre n ≥ 1, calculez à la fois fib (n) et fib (n-1). Vous avez donc besoin d'une fonction qui renvoie deux résultats, appelons cette fonction fib2.

L'implémentation est assez simple:

function fib2 (n) -> (fibn, fibnm1) {
    if n ≤ 1 { return (1, 1) }
    let (fibn, fibnm1) = fib2 (n-1)
    return (fibn + fibnm1, fibn)
}