Récursivité en Python
Le terme récursivité peut être défini comme le processus de définition de quelque chose en termes de lui-même. En termes simples, il s'agit d'un processus dans lequel une fonction s'appelle directement ou indirectement.
Avantages de l'utilisation de la récursivité
- Une fonction complexe peut être divisée en sous-problèmes plus petits en utilisant la récursivité.
- La création de séquences est plus simple grâce à la récursion que par l'utilisation d'une itération imbriquée.
- Les fonctions récursives rendent le code simple et efficace.
Inconvénients de l'utilisation de la récursivité
- Beaucoup de mémoire et de temps sont consommés par les appels récursifs, ce qui rend leur utilisation coûteuse.
- Les fonctions récursives sont difficiles à déboguer.
- Le raisonnement derrière la récursivité peut parfois être difficile à comprendre.
Syntaxe:
def func(): <-- | | (recursive call) | func() ----
Exemple 1: Une séquence de Fibonacci est la séquence entière de 0, 1, 1, 2, 3, 5, 8….
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> > if> n <> => 1> :> > return> n> > else> :> > return> (recursive_fibonacci(n> -> 1> )> +> recursive_fibonacci(n> -> 2> ))> n_terms> => 10> # check if the number of terms is valid> if> n_terms <> => 0> :> > print> (> 'Invalid input ! Please input a positive value'> )> else> :> > print> (> 'Fibonacci series:'> )> for> i> in> range> (n_terms):> > print> (recursive_fibonacci(i))> |
Sortir
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Exemple 2 : La factorielle de 6 est notée 6 ! = 1*2*3*4*5*6 = 720.
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> > if> n> => => 1> :> > return> n> > else> :> > return> n> *> recursive_factorial(n> -> 1> )> # user input> num> => 6> # check if the input is valid or not> if> num <> 0> :> > print> (> 'Invalid input ! Please enter a positive number.'> )> elif> num> => => 0> :> > print> (> 'Factorial of number 0 is 1'> )> else> :> > print> (> 'Factorial of number'> , num,> '='> , recursive_factorial(num))> |
Sortir
Factorial of number 6 = 720
Qu'est-ce que la récursion de queue ?
Un type unique de récursion où la dernière procédure d'une fonction est un appel récursif. La récursion peut être automatisée en exécutant la requête dans le cadre de pile actuel et en renvoyant la sortie au lieu de générer un nouveau cadre de pile. La récursion de queue peut être optimisée par le compilateur, ce qui la rend meilleure que les fonctions récursives sans queue.
Est-il possible d'optimiser un programme en utilisant une fonction récursive de queue au lieu d'une fonction récursive non-queue ?
En considérant la fonction donnée ci-dessous afin de calculer la factorielle de n, nous pouvons observer que la fonction ressemble au début à une queue-récursive mais qu'il s'agit d'une fonction non-queue-récursive. Si nous observons attentivement, nous pouvons voir que la valeur renvoyée par Recur_facto(n-1) est utilisée dans Recur_facto(n), donc l'appel à Recur_facto(n-1) n'est pas la dernière chose effectuée par Recur_facto(n).
Python3
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > > if> (n> => => 0> ):> > return> 1> > > return> n> *> Recur_facto(n> -> 1> )> > # print the result> print> (Recur_facto(> 6> ))> |
Sortir
720
Nous pouvons écrire la fonction donnée Recur_facto comme une fonction récursive de queue. L'idée est d'utiliser un argument supplémentaire et dans le deuxième argument, nous intégrons la valeur de la factorielle. Lorsque n atteint 0, renvoie la valeur finale de la factorielle du nombre souhaité.
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a> => 1> ):> > > if> (n> => => 0> ):> > return> a> > > return> Recur_facto(n> -> 1> , n> *> a)> > # print the result> print> (Recur_facto(> 6> ))> |
Sortir
720
