Boucles récursives ou en boucle

123

Je lisais quelques articles sur les entretiens de développement, en particulier sur les questions techniques et les tests posés lors des entretiens, et je suis tombé à plusieurs reprises sur des paroles du genre "Ok, tu as résolu le problème en boucle while, peux-tu maintenant le faire avec récursion ", ou" tout le monde peut résoudre ce problème avec une boucle de 100 lignes, mais peut-il le faire avec une fonction récursive de 5 lignes? " etc.

Ma question est la suivante: la récursivité est-elle généralement meilleure que si / pendant / pour les constructions?

Honnêtement, j’ai toujours pensé que la récursion n’était pas préférable, car elle se limitait à la mémoire de la pile, qui est beaucoup plus petite que le tas. Effectuer un grand nombre d’appels de fonction / méthode est également sous-optimal du point de vue des performances, mais je peux se tromper...

Shivan Dragon
la source
73
Au sujet de la récursion, cela semble assez intéressant.
dan_waterworth
4
@dan_waterworth également, cela aiderait: google.fr/… mais je semble toujours manquer de l'épeler: P
Dragon Shivan
@ShivanDragon Je le pensais bien ^ _ ^ Je pense que c'est très bien que je l'ai posté hier :-)
Neal
2
Dans les environnements embarqués dans lesquels j'ai travaillé en récursivité, on est au mieux mal vu et on vous fait flageller publiquement au pire. L'espace de pile limité en fait le rend illégal.
Fred Thomsen

Réponses:

192

La récursivité n'est pas intrinsèquement meilleure ou pire que les boucles - chacune présente des avantages et des inconvénients, et ceux-ci dépendent même du langage de programmation (et de la mise en œuvre).

Techniquement, les boucles itératives conviennent mieux aux systèmes informatiques classiques au niveau matériel: au niveau code machine, une boucle est simplement un test et un saut conditionnel, alors que la récursivité (implémentée naïvement) implique de pousser un cadre de pile, de sauter, de revenir en arrière et de revenir en arrière. de la pile. OTOH, de nombreux cas de récursion (en particulier ceux qui sont trivialement équivalents à des boucles itératives) peuvent être écrits de manière à éviter la pile push / pop; cela est possible lorsque l'appel de fonction récursif est la dernière chose qui se passe dans le corps de la fonction avant de renvoyer, et qu'il est communément appelé optimisation d'appel final (ou optimisation de récursivité finale ). Une fonction récursive correctement optimisée pour les appels en sortie est généralement équivalente à une boucle itérative au niveau du code machine.

Une autre considération est que les boucles itératives nécessitent des mises à jour d'état destructives, ce qui les rend incompatibles avec la sémantique du langage pur (sans effets secondaires). C'est la raison pour laquelle les langages purs tels que Haskell n'ont pas du tout de construction de boucle et que de nombreux autres langages de programmation fonctionnels en manquent complètement ou les évitent autant que possible.

La raison pour laquelle ces questions apparaissent si souvent dans les entretiens, c’est parce que, pour y répondre, vous devez comprendre de nombreux concepts de programmation essentiels - variables, appels de fonction, étendue et bien sûr boucles et récursions -, et vous avez apporter la flexibilité mentale à la table qui vous permet d'aborder un problème sous deux angles radicalement différents et de passer d'une manifestation à l'autre du même concept.

L'expérience et la recherche suggèrent qu'il existe une ligne de démarcation entre les personnes qui ont la capacité de comprendre les variables, les pointeurs et la récursion, et celles qui ne le sont pas. Presque tout le reste de la programmation, y compris les frameworks, les API, les langages de programmation et leurs cas extrêmes, peut être acquis par l'étude et l'expérience, mais si vous êtes incapable de développer une intuition pour ces trois concepts de base, vous ne pouvez pas être programmeur. Traduire une simple boucle itérative en une version récursive est le moyen le plus rapide de filtrer les non-programmeurs - même un programmeur plutôt inexpérimenté peut le faire en 15 minutes, et c'est un problème très agnostique pour le une langue de leur choix au lieu de trébucher sur des idiosyncracies.

Si vous rencontrez une question comme celle-ci lors d'une interview, c'est bon signe: cela signifie que l'employeur éventuel recherche des personnes capables de programmer, et non des personnes ayant mémorisé le manuel d'un outil de programmation.

tdammers
la source
3
Votre réponse me plait le plus, car elle aborde les aspects les plus importants d’une réponse à cette question, elle explique les principaux aspects techniques et donne également un bon aperçu de la manière dont cette question s’intègre dans le domaine de la programmation.
Shivan Dragon
1
J'ai également remarqué un motif dans une programmation de synchronisation dans laquelle les boucles sont évitées au profit d'appels récursifs sur un itérateur contenant une méthode .next (). Je suppose qu'il empêche longtemps le code en cours d'exécution de devenir trop gourmand en ressources processeur.
Evan Plaice
1
La version itérative implique également de pousser et d'afficher des valeurs. Il vous suffit d'écrire manuellement le code pour le faire. La version récursive pousse l’état sur la pile dans un algorithme itératif que vous devez généralement simuler manuellement en poussant l’état dans une structure donnée. Seuls les algorithmes les plus triviaux n'ont pas besoin de cet état et dans ces cas, le compilateur peut généralement détecter la récursion de la queue et implanter une solution itérative.
Martin York
1
@tdammers Pourriez-vous me dire où je peux lire l'étude que vous avez mentionnée "L'expérience et la recherche suggèrent qu'il existe une ligne de démarcation entre les gens ..." Cela semble être très intéressant pour moi.
Yoo Matsuo
2
Une chose que vous avez oublié de mentionner, le code itératif a tendance à mieux fonctionner lorsque vous avez affaire à un seul thread d'exécution, mais les algorithmes récursifs ont tendance à se prêter à être exécutés dans plusieurs threads.
GordonM
37

Ça dépend.

  • Certains problèmes se prêtent très bien aux solutions récursives, par exemple le tri rapide
  • Certaines langues ne supportent pas vraiment la récursivité, par exemple les premiers FORTRAN
  • Certaines langues supposent la récursion comme moyen principal de bouclage, par exemple Haskell

Il convient également de noter que la prise en charge de la récursion de la queue rend les boucles récursives et itératives de la queue équivalentes, c'est-à-dire que la récursivité ne gaspille pas toujours la pile.

De plus, un algorithme récursif peut toujours être implémenté de manière itérative en utilisant une pile explicite .

Enfin, je noterais qu'une solution à cinq lignes est probablement toujours meilleure qu'une solution à 100 lignes (en supposant qu'elles soient réellement équivalentes).

jk.
la source
5
Bonne réponse (+1). "Une solution à 5 lignes est probablement toujours meilleure qu'une solution à 100 lignes": je pense que la concision n'est pas le seul avantage de la récursivité. L'utilisation d'un appel récursif vous oblige à rendre explicites les dépendances fonctionnelles entre les valeurs de différentes itérations.
Giorgio
4
Les solutions plus courtes ont tendance à être meilleures, mais il existe une chose qui serait trop laconique.
dan_waterworth
5
@dan_waterworth comparé à "100 line", il est plutôt difficile d'être trop concis
Gnat
4
@Giorgio, Vous pouvez réduire la taille des programmes en supprimant le code inutile ou en rendant implicite des éléments explicites. Tant que vous vous en tenez à l'ancien, vous améliorez la qualité.
dan_waterworth
1
@jk, je pense que c'est une autre façon de rendre implicite une information explicite. Les informations sur l'utilisation d'une variable sont supprimées de son nom, car elles sont explicites et insérées dans son utilisation, qui est implicite.
dan_waterworth
17

Il n'y a pas de définition universellement acceptée du terme «meilleur» en matière de programmation, mais je vais comprendre que cela signifie «plus facile à maintenir / à lire».

La récursivité a un pouvoir plus expressif que les constructions en boucle itératives: je dis cela parce qu'une boucle while est équivalente à une fonction récursive et que les fonctions récursives n'ont pas besoin d'être récursives. Les constructions puissantes sont généralement une mauvaise chose, car elles vous permettent de faire des choses difficiles à lire. Cependant, la récursivité vous donne la possibilité d'écrire des boucles sans utiliser la mutabilité et, à mon sens, la mutabilité est beaucoup plus puissante que la récursion.

Donc, du pouvoir expressif faible au pouvoir expressif élevé, les constructions en boucle s'empilent comme suit:

  • Queue fonctions récursives qui utilisent des données immuables,
  • Fonctions récursives utilisant des données immuables,
  • Alors que les boucles qui utilisent des données mutables,
  • Queue fonctions récursives qui utilisent des données mutables,
  • Fonctions récursives utilisant des données mutables,

Idéalement, vous utiliseriez les constructions les moins expressives possible. Bien sûr, si votre langue ne prend pas en charge l'optimisation des appels en queue, cela peut également influer sur votre choix de construction en boucle.

dan_waterworth
la source
1
"une boucle while est équivalente à une fonction récursive finale et les fonctions récursives ne doivent pas nécessairement être récursives" ": +1. Vous pouvez simuler la récursivité au moyen d'une boucle while + d'une pile.
Giorgio
1
Je ne suis pas sûr d'être d'accord à 100%, mais c'est certainement une perspective intéressante, donc +1 pour cela.
Konrad Rudolph
+1 pour une bonne réponse et aussi pour mentionner que certaines langues (ou compilateurs) n'optimisent pas les appels en aval.
Shivan Dragon
@Giorgio, "Vous pouvez simuler la récursivité à l'aide d'une boucle while + d'une pile", c'est pourquoi j'ai dit le pouvoir expressif. En termes de calcul, ils sont également puissants.
dan_waterworth
@ dan_waterworth: Exactement, et comme vous l'avez dit dans votre réponse, la récursivité seule est plus expressive qu'une boucle while car vous devez ajouter une pile à une boucle while pour simuler la récursivité.
Giorgio
7

La récursivité est souvent moins évidente. Moins évident est plus difficile à maintenir.

Si vous écrivez for(i=0;i<ITER_LIMIT;i++){somefunction(i);}dans le flux principal, vous indiquez parfaitement que vous écrivez une boucle. Si vous écrivez, somefunction(ITER_LIMIT);vous ne précisez pas vraiment ce qui va se passer. Ne voir que du contenu: les somefunction(int x)appels somefunction(x-1)vous indiquent qu'il s'agit en réalité d'une boucle utilisant des itérations. En outre, vous ne pouvez pas facilement définir une condition d'échappement avec break;un résultat à mi-chemin des itérations. Vous devez soit ajouter une condition qui sera renvoyée complètement, soit renvoyer une exception. (et les exceptions ajoutent encore de la complexité ...)

Essentiellement, si le choix est évident entre itération et récursivité, faites de l’intuitif. Si l'itération fait le travail facilement, sauvegarder 2 lignes vaut rarement la peine qu'il peut créer à long terme.

Bien sûr, si cela vous épargne 98 lignes, c'est une tout autre chose.

Il y a des situations pour lesquelles la récursion convient tout simplement parfaitement et elles ne sont pas vraiment rares. Traversée des structures en arborescence, des réseaux à liaisons multiples, des structures pouvant contenir son propre type, des tableaux multidimensionnels déchiquetés, essentiellement tout ce qui n'est ni un vecteur simple, ni un tableau de dimensions fixes. Si vous traversez un chemin connu et droit, parcourez-le. Si vous plongez dans l'inconnu, recurse.

Essentiellement, si somefunction(x-1)vous voulez appeler de l'intérieur de vous plus d'une fois par niveau, oubliez les itérations.

... Écrire des fonctions de manière itérative pour des tâches optimisées par la récursion est possible mais peu agréable. Où que vous utilisiez int, vous avez besoin de quelque chose comme stack<int>. Je l'ai fait une fois, plus comme exercice que pour des raisons pratiques. Je peux vous assurer que lorsque vous serez confronté à une telle tâche, vous n'aurez plus de doutes comme ceux que vous avez exprimés.

SF.
la source
10
Ce qui est évident et ce qui est moins évident dépend en partie de ce que vous êtes habitué. L'itération a été plus souvent utilisée dans les langages de programmation car elle est plus proche du mode de fonctionnement de la CPU (c'est-à-dire qu'elle utilise moins de mémoire et s'exécute plus rapidement). Mais si vous avez l'habitude de penser de manière inductive, la récursivité peut être aussi intuitive.
Giorgio
5
"S'ils voient un mot clé de boucle, ils savent qu'il s'agit d'une boucle. Mais il n'y a pas de mot clé recurse, ils peuvent le reconnaître uniquement en voyant f (x-1) dans f (x).": Lorsque vous appelez une fonction récursive, vous le faites veut pas savoir qu'il est récursif. De même, lorsque vous appelez une fonction contenant une boucle, vous ne voulez pas savoir qu'elle contient une boucle.
Giorgio
3
@SF: Oui, mais vous ne pouvez le voir que si vous regardez le corps de la fonction. En cas de boucle, vous voyez la boucle, en cas de récursivité, vous voyez que la fonction s’appelle elle-même.
Giorgio
5
@SF: Pour moi, cela ressemble un peu à un raisonnement circulaire: "Si dans mon intuition, c'est une boucle, alors c'est une boucle." mappeut être défini comme une fonction récursive (voir par exemple haskell.org/tutorial/functions.html ), même s'il est intuitivement clair qu'il parcourt une liste et applique une fonction à chaque membre de la liste.
Giorgio
5
@SF, ce mapn'est pas un mot clé, c'est une fonction normale, mais c'est un peu sans importance. Lorsque les programmeurs fonctionnels utilisent la récursivité, ce n'est généralement pas parce qu'ils veulent effectuer une séquence d'actions, c'est parce que le problème à résoudre peut être exprimé sous la forme d'une fonction et d'une liste d'arguments. Le problème peut alors être réduit à une autre fonction et à une autre liste d'arguments. Finalement, vous avez un problème qui peut être résolu de manière triviale.
dan_waterworth
6

Comme d'habitude, ceci est généralement irrévocable car il existe des facteurs supplémentaires, qui sont en pratique très inégaux entre les cas et inégaux les uns des autres dans un cas d'utilisation. Voici certaines des pressions.

  • Un code court et élégant est en général supérieur au code long et complexe.
  • Cependant, le dernier point est quelque peu invalidé si votre base de développeurs n'est pas habituée à la récursivité et ne veut pas / ne peut pas apprendre. Cela pourrait même devenir légèrement négatif plutôt que positif.
  • La récursivité peut être préjudiciable à l'efficacité si, dans la pratique , vous avez besoin d'appels profondément imbriqués et que vous ne pouvez pas utiliser la récursion arrière (ou que votre environnement ne peut pas optimiser la récursivité arrière).
  • La récursivité est également mauvaise dans de nombreux cas si vous ne pouvez pas correctement mettre en cache les résultats intermédiaires. Par exemple, l'exemple courant d'utilisation de la récursivité dans les arbres pour calculer les nombres de Fibonacci est terriblement mauvais si vous ne cachez pas. Si vous cachez, c'est simple, rapide, élégant et tout à fait merveilleux.
  • La récursivité ne s'applique pas dans certains cas, elle est aussi efficace que l'itération dans d'autres et absolument nécessaire dans d'autres encore. Les récursions ne facilitent généralement pas la récursivité. La récurrence peut utilement itérer dans les flux de données. Itérer sur des structures de données dynamiques multidimensionnelles (par exemple, des labyrinthes, des arbres d'objets, etc.) est quasiment impossible sans récurrence, explicite ou implicite. Notez que dans ces cas-là, la récursion explicite est bien meilleure qu'implicite - rien n'est plus pénible que de lire du code où quelqu'un implémentait sa propre pile de bogues ad-hoc, incomplète et boguée dans la langue, juste pour éviter le mot R effrayant.
Kilian Foth
la source
Qu'entendez-vous par mise en cache par rapport à la récursivité?
Giorgio
@ Giorgio vraisemblablement mémoization
jk.
Feh. Si votre environnement n'optimise pas les appels en aval, vous devriez trouver un meilleur environnement. Si vos développeurs ne sont pas familiarisés avec la récursivité, vous devez trouver de meilleurs développeurs. Avoir des normes, les gens!
CA McCann
1

La récursion consiste à répéter l'appel à la fonction, la boucle, à répéter le saut à placer en mémoire.

Devrait également être mentionné à propos du dépassement de pile - http://en.wikipedia.org/wiki/Stack_overflow

okobaka
la source
1
Récursion signifie une fonction dont la définition implique de s’appeler.
Hardmath
1
Bien que votre définition simple ne soit pas exacte à 100%, vous êtes le seul à avoir mentionné les débordements de pile.
Qix
1

Cela dépend vraiment de la commodité ou de l'exigence:

Si vous utilisez le langage de programmation Python , il prend en charge la récursivité, mais il existe par défaut une limite pour la profondeur de récursivité (1000). Si cela dépasse la limite, nous aurons une erreur ou une exception. Cette limite peut être changée, mais si nous le faisons, nous pouvons rencontrer des situations anormales dans la langue.

À ce stade (nombre d'appels supérieur à la profondeur de récursivité), nous devons préférer les constructions de boucle. Je veux dire, si la taille de la pile n'est pas suffisante, nous devons préférer les constructions en boucle.

usernaveen
la source
3
Voici un blog de Guido van Rossum expliquant pourquoi il ne souhaite pas une optimisation de la récursion de queue en Python (supportant la notion selon laquelle différentes langues adoptent des approches tactiques distinctes).
Hardmath
-1

Utilisez le modèle de conception de stratégie.

  • La récursion est propre
  • Les boucles sont (sans doute) efficaces

En fonction de votre charge (et / ou d'autres conditions), choisissez-en une.

Pravin Sonawane
la source
5
Attends quoi? Comment le modèle de stratégie s'intègre-t-il ici? Et la deuxième phrase sonne comme une phrase vide.
Konrad Rudolph
@ KonradRudolph je voudrais aller pour la récursion. Pour les très grands ensembles de données, je basculerais en boucles. C'est ce que je voulais dire. Je m'excuse si ce n'était pas clair.
Pravin Sonawane
3
Ah Eh bien, je ne suis toujours pas sûr que cela puisse être appelé «modèle de conception de stratégie», qui a un sens très fixe et que vous utilisez métaphoriquement. Mais maintenant au moins je vois où vous allez.
Konrad Rudolph
@ KonradRudolph a appris une leçon importante. Expliquez-moi bien ce que vous voulez dire .. Merci .. cela a aidé .. :)
Pravin Sonawane
2
@Pravin Sonawane: Si vous pouvez utiliser l'optimisation de la récursion de la queue, vous pouvez également utiliser la récursivité sur de très grands ensembles de données.
Giorgio