Quels sont les avantages et les inconvénients de la récursivité?

La récursivité signifie qu'une fonction appelle à plusieurs reprises

Il utilise la pile système pour accomplir sa tâche. Comme la pile utilise L'approche LIFO et quand une fonction est appelée Le contrôlé est déplacé à l'endroit où la fonction est définie qui a elle est stockée dans la mémoire avec une certaine adresse, Cette adresse est stockée dans la pile

Deuxièmement, cela réduit la complexité temporelle d'un programme.

Bien que peu hors sujet, un peu lié. À lire absolument. : Récursivité vs Itération

Tous les algorithmes peuvent être définis récursivement. Qui le rend beaucoup plus facile à visualiser et à prouver.

Certains algorithmes (par exemple, la fonction Ackermann) ne peuvent pas (facilement) être spécifiés itérativement.

Une implémentation récursive utilisera plus de mémoire qu'une boucle si l'optimisation des appels de queue ne peut pas être effectuée. Alors que l'itération peut utiliser moins de mémoire qu'une fonction récursive qui ne peut pas être optimisée, elle a certaines limites dans son pouvoir expressif.

Personnellement, je préfère utiliser une fonction itérative plutôt qu'une fonction récursive. Surtout si votre fonction a une logique complexe/lourde et que le nombre d'itérations est important. Ceci parce qu'avec chaque appel récursif, la pile d'appels augmente. Il pourrait potentiellement planter la pile si vos opérations sont trop grandes et ralentissent également le processus.

Pour commencer:

Avantages:

• c'est la façon unique d'implémenter un nombre variable de boucles imbriquées (et la seule façon élégante d'implémenter un grand nombre constant de boucles imbriquées).

Inconvénients:

• les méthodes récursives lancent souvent une exception StackOverflowException lors du traitement de grands ensembles. Boucles récursives n'ont pas ce problème.

Tout algorithme implémenté en utilisant la récursivité peut également être implémenté en utilisant l'itération.

Pourquoi pas pour utiliser la récursivité

1. Il est généralement plus lent en raison de la surcharge de maintenance de la pile.
2. Il utilise généralement plus de mémoire pour la pile.

Pourquoi à utiliser la récursivité

1. la récursivité ajoute de la clarté et (parfois) réduit le temps nécessaire à l'écriture et au débogage du code (mais ne réduit pas nécessairement l'espace requis ou la vitesse de exécution).
2. Réduit la complexité du temps.
3. fonctionne mieux dans la résolution de problèmes basés sur des structures arborescentes.

Par exemple, le problème de la Tour de Hanoi est plus facilement résolu en utilisant la récursivité que l'itération.

Expressivité

La plupart des problèmes sont naturellement exprimés par la récursivité comme Fibonacci, le tri par fusion et le tri rapide. À cet égard, le code est écrit pour les humains, pas des machines.

Immuabilité

Les solutions itératives reposent souvent sur des variables temporaires variables qui rendent le code difficile à lire. Cela peut être évité avec la récursivité.

Performance

La récursivité n'est pas conviviale. La pile peut déborder lorsque la récursivité n'est pas bien conçue ou l'optimisation de la queue n'est pas prise en charge.

Une situation se poserait où vous devriez abandonner la récursivité dans un problème où la récursivité semble être à votre avantage, car pour les problèmes où votre récursivité devrait se produire des milliers de fois, cela entraînerait une erreur stackoverflow même si votre code n'est pas coincé dans une récursivité infinie. La plupart des langages de programmation vous limitent à un certain nombre d'appels de pile, donc si votre récursivité dépasse cette limite, vous pouvez envisager de ne pas utiliser la récursivité.