Qu'est-ce que la fonction récursive?
La fonction s'appelle encore et encore jusqu'à ce qu'elle remplisse une condition récursive. Une fonction de récursivité décompose le problème en problèmes plus petits et appelle sa propre logique pour résoudre le problème plus petit. Cette technique est connue sous le nom de diviser pour régner. Il est utilisé en mathématiques et dans le domaine de l'informatique.
La fonction récursive comprend un cas de base (ou cas terminal) et un cas récursif. Dans le cas de base, vous pouvez considérer le problème majeur à résoudre et le cas récursif divise le problème en parties plus petites jusqu'à ce qu'il atteigne un niveau où il peut être résolu facilement. Un cas récursif peut renvoyer un résultat ou il peut s'appeler à nouveau pour diviser davantage le problème. Chaque fois que le problème se décompose en un problème plus petit, la fonction qui est appelée récursivement enregistre l'état de l'appel et attend le résultat d'elle-même après avoir décomposé le problème.
Fonction récursive en Python
Le concept de récursivité reste le même en Python. La fonction s'appelle pour décomposer le problème en problèmes plus petits. L'exemple le plus simple que nous pourrions penser à la récursivité serait de trouver la factorielle d'un nombre.
Disons que nous devons trouver la factorielle du nombre 5 => 5! (Notre problème)
Pour en trouver 5! le problème peut être divisé en plus petits 5! => 5 x 4!
Alors, pour en avoir 5! Nous devons en trouver 4! et multipliez-le par 5.
Continuons à diviser le problème
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Quand il atteint le plus petit morceau c'est-à-dire, en obtenant la factorielle de 1, nous pouvons retourner le résultat sous la forme
Prenons un exemple de pseudo-code: -
Algorithme pour factoriel
Voyons l'algorithme pour factorielle:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Appels de fonction
Supposons que nous trouvons une factorielle de 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Le résultat final sera 120 où nous avons commencé l'exécution de la fonction. Notre fonction de récursivité s'arrête lorsque le nombre est tellement réduit que le résultat peut être obtenu.
- Le premier appel qui obtient le factoriel de 5 se traduira par une condition récursive où il sera ajouté à la pile et un autre appel sera effectué après avoir réduit le nombre à 4.
- Cette récursivité continuera d'appeler et de diviser le problème en petits morceaux jusqu'à ce qu'il atteigne l'état de base.
- La condition de base ici est lorsque le nombre est 1.
- Chaque fonction récursive a sa propre condition récursive et une condition de base.
Avantages et inconvénients de la fonction récursive Python
- L'exécution de la récursivité est telle qu'elle ne fera aucun calcul tant qu'elle n'aura pas atteint la condition de base.
- En atteignant les conditions de base, vous risquez de manquer de mémoire.
- Dans un gros problème où il peut y avoir un million d'étapes ou on peut dire qu'un million de récursions pour faire le programme pourraient finir par donner une erreur de mémoire ou un défaut de segmentation.
- 1000000! = 1000000 * 999999! =?
- La récursivité est différente de l'itération, elle n'est pas mise à l'échelle comme une méthode itérative.
- Différentes langues ont différentes optimisations pour la récursivité.
- Dans de nombreuses langues, la méthode itérative fonctionnerait mieux que la récursivité.
- Chaque langue a certaines restrictions sur la profondeur de récursivité que vous pourriez rencontrer lors de la résolution de problèmes importants.
- Parfois, il est difficile de comprendre les problèmes complexes de la récursivité alors que c'est assez simple avec l'itération.
Quelques pros
- Dans certains cas, la récursivité est un moyen pratique et plus rapide à utiliser.
- Très utile dans la traversée de l'arborescence et la recherche binaire.
Code Python - Récursion vs Itération
Nous avons compris ce qu'est la récursivité et comment cela fonctionne en Python, car nous savons que tous les langages ont une implémentation différente de la récursivité pour la mémoire et les optimisations de calcul. Il peut y avoir un cas où l'itération serait plus rapide que la récursivité.
Ici, nous comparerions à la fois la méthode de récursivité et d'itération pour voir comment Python fonctionne dans les deux cas.
1. Code de récursion pour le factoriel
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Problème factoriel utilisant l'itération (bouclage)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Impression des résultats
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Production:
Comme nous pouvons le voir, les deux donnent la même sortie que nous avons écrit la même logique. Ici, nous ne voyons aucune différence d'exécution.
Ajoutons du code temporel pour obtenir plus d'informations sur l'exécution de la récursivité et de l'itération en Python.
Nous allons importer la bibliothèque «time» et vérifier le temps de récursivité et d'itération nécessaires pour retourner le résultat.
4. Code avec calcul du temps
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Nous ferons des exécutions répétées avec une valeur différente pour factorielle et verrons les résultats. Les résultats ci-dessous peuvent varier d'une machine à l'autre. Nous avons utilisé le MacBook Pro 16 Go de RAM i7.
Nous utilisons Python 3.7 pour l'exécution
Cas 1: - Factoriel de 6:
Cas 2: Factoriel de 50:
Cas 3: Factorielle de 100:
Cas 4: Factorielle de 500:
Cas 5: Factorielle de 1000:
Nous avons analysé les deux méthodes dans un problème différent. De plus, les deux ont eu des performances similaires sauf le cas 4.
Dans le cas 5, nous avons eu une erreur en le faisant avec la récursivité.
Python a obtenu une restriction sur la profondeur maximale que vous pouvez utiliser avec la récursivité, mais le même problème que j'ai pu résoudre avec l'itération.
Python a des restrictions contre le problème de débordement. Python n'est pas optimisé pour la récursivité de queue, et la récursivité non contrôlée provoque un débordement de pile.
La fonction «sys.getrecursionlimit ()» vous indiquerait la limite de récursivité.
La limite de récursivité peut être modifiée mais non recommandée, elle peut être dangereuse.
Conclusion - Fonction récursive Python
- La récursivité est une solution pratique pour certains problèmes comme la traversée des arbres et d'autres problèmes.
- Python n'est pas un langage de programmation fonctionnel et nous pouvons voir que la pile de récursivité n'est pas optimisée par rapport à l'itération.
- Nous devrions utiliser l'itération dans notre algorithme car elle est plus optimisée en Python et vous donne une meilleure vitesse.
Articles recommandés
Ceci est un guide de la fonction récursive en Python. Nous discutons ici de ce qu'est la fonction récursive, la fonction récursive en Python, l'algorithme pour factorielle, etc. Vous pouvez également parcourir nos autres articles suggérés pour en savoir plus–
- Factorial en Python
- Commandes Spark Shell
- Meilleurs compilateurs C
- Types d'algorithmes
- Programme factoriel en JavaScript
- Guide de la liste des commandes du shell Unix
- Types de formulaires dans React avec des exemples