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...
la source
Réponses:
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.
la source
Ça dépend.
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).
la source
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:
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.
la source
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: lessomefunction(int x)
appelssomefunction(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 avecbreak;
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 commestack<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.la source
map
peut ê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.map
n'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.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.
la source
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
la source
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.
la source
Utilisez le modèle de conception de stratégie.
En fonction de votre charge (et / ou d'autres conditions), choisissez-en une.
la source