Avez-vous déjà été pris dans un cycle apparemment sans fin où un problème continue de se diviser en fragments plus petits ?
Si tel est le cas, vous êtes peut-être tombé sur le monde passionnant de la récursivité. Bien que cela puisse sembler difficile à comprendre, ne vous inquiétez pas ! Dans cet article, nous allons faire un voyage intéressant pour en savoir plus sur les types de récursivité.
Alors bouclez votre ceinture alors que nous explorons de nombreuses approches récursives. Préparez-vous à entrer dans le domaine fascinant de la récursivité et observez sa remarquable capacité à résoudre des problèmes complexes.
Que sont exactement les récursions ?
En termes simples, la récursivité est une technique de programmation puissante qui inclut une fonction qui s'appelle pendant l'exécution. C'est comme regarder dans un miroir et voir une image à l'intérieur d'une image, résultant en un cycle autoréférentiel.
Nous pouvons résoudre de gros problèmes en utilisant la récursivité en les divisant en sous-problèmes plus petits et plus gérables.
Cela revient à assembler un puzzle, où une pièce est liée à d'autres parties pour produire une image complète. La récursivité nous permet de résoudre des problèmes de manière élégante et efficace en répétant le même ensemble d'instructions avec différentes entrées.
1-Récursivité directe
La récursivité directe est le type de récursivité le plus basique, dans lequel une fonction s'appelle elle-même directement. Cela implique de diviser un problème problématique en sous-problèmes plus petits jusqu'à ce qu'un cas de base soit atteint, ce qui conduit à la résiliation.
La fonction récursive s'appelle elle-même avec différentes entrées, permettant de répéter l'exécution d'un même ensemble d'instructions. Chaque invocation s'appuie sur la précédente, se rapprochant progressivement du cas de base qui provoque la fin de la récursivité.
Vérifions cet exemple.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Sortie :
5
4
3
2
1
2-Récursion indirecte
La récursivité indirecte ajoute une touche intrigante au chemin récursif. Contrairement à la récursivité directe, qui implique qu'une fonction s'appelle elle-même explicitement, la récursivité indirecte inclut une chaîne d'appels de fonction.
Une fonction en appelle une autre, qui peut ensuite appeler la fonction d'origine ou toute autre fonction qui revient finalement à l'original. Ce réseau interconnecté d'appels de fonction produit une danse passionnante dans laquelle plusieurs fonctions collaborent pour résoudre un problème.
Mise en situation :
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Sortie :
A: 3
B: 2
A: 1
3-Récursion linéaire
Envisagez un voyage sur une route droite, une étape à la fois, jusqu'à ce que vous arriviez à votre objectif. Cette technique séquentielle est incarnée par la récursivité linéaire, dans laquelle une fonction effectue un seul appel récursif à chaque itération de fonction.
À chaque appel récursif, le processus récursif se rapproche d'un cas de base en réduisant la taille du problème. Il procède de manière claire et linéaire, résolvant les sous-problèmes un par un jusqu'à ce que la réponse ultime soit atteinte.
Mise en situation :
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Sortie :
120
Récursivité à 4 arbres
Lorsqu'une fonction se ramifie en plusieurs appels récursifs, nous entrons dans le monde de la récursivité arborescente. Une fonction dans la récursivité arborescente génère de nombreux appels récursifs, chacun résolvant un sous-problème distinct, tout comme le font les branches d'un arbre.
Cette structure de ramification permet l'investigation simultanée de plusieurs itinéraires, décomposant efficacement les problèmes complexes en composants plus petits et interdépendants.
Mise en situation :
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Sortie :
8
Récursivité à 5 imbrications
La récursivité imbriquée ajoute un degré passionnant de complexité à l'univers récursif. Dans cette forme de récursivité, une fonction incorpore un appel récursif comme argument dans un autre appel récursif.
L'appel récursif interne agit sur une valeur qui dépend de l'appel récursif externe. La complexité augmente avec chaque invocation imbriquée, aboutissant à un modèle intrigant d'appels récursifs imbriqués.
Mise en situation :
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Résultat:
91
Récursivité à 6 queues
La récursivité terminale est une technique d'optimisation des algorithmes récursifs qui peut améliorer leurs performances. L'appel récursif apparaît comme l'action finale d'une fonction avec récursivité terminale, making.
Puisqu'il n'y a pas d'opérations en attente après l'appel récursif, le compilateur ou l'interpréteur peut simplifier la récursivité en la remplaçant par un simple saut.
Cette approche d'optimisation, connue sous le nom d'optimisation des appels de queue, réduit la nécessité pour chaque appel récursif de conserver un cadre de pile, ce qui se traduit par une vitesse accrue et une utilisation réduite de la mémoire.
Mise en situation :
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Dehors:
120
7-Récursivité sans queue
Contrairement à la récursivité terminale, la récursivité non terminale implique des activités supplémentaires effectuées après l'appel récursif dans une fonction. Avant que d'autres actions puissent être effectuées, chaque appel récursif doit se terminer et revenir.
Par conséquent, jusqu'à ce que le cas de base soit atteint et que la récursivité se termine, une pile d'opérations en cours est maintenue. La récursivité non terminale utilise fréquemment plus de mémoire et est moins efficace que la récursivité terminale, mais elle reste un outil utile pour résoudre divers problèmes.
Mise en situation :
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Sortie :
15
Emballer
La récursivité est un concept intrigant en programmation. Il nous permet d'aborder des problèmes complexes de manière récursive et autoréférentielle.
Il offre une méthode distincte de réflexion et de résolution des problèmes, en les décomposant en morceaux plus petits et plus gérables. Lorsque vous travaillez avec la récursivité, cependant, il est essentiel de prêter attention à certains points.
Vous devez identifier les cas de base appropriés qui permettent à la récursivité de se terminer. S'ils ne sont pas présents, la fonction peut continuer à s'appeler indéfiniment.
Deuxièmement, en fonction du scénario en question, la sélection du type de récursivité approprié peut conduire à des solutions plus efficaces et plus élégantes. Essayez de trouver ce qui fonctionne le mieux pour le problème de la main. Lorsque vous travaillez avec de vastes profondeurs de récursivité, soyez conscient des dangers potentiels tels que le débordement de pile.
Soyez sympa! Laissez un commentaire