Exemple d'analyse de la définition et de l'utilisation des fonctions récursives Python

Cet article présente principalement la définition et l'utilisation de Pythonfonction récursive, et analyse les principes, les techniques de mise en œuvre et les Notes, les amis dans le besoin peuvent se référer à

Cet article explique la définition et l'utilisation des fonctions récursives Python avec des exemples. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Fonction récursive

Dans la fonction, vous pouvez appeler d'autres fonctions. Une fonction est récursive si elle s'appelle en interne.

Par exemple, calculons la factorielle n ! = 1 * 2 * 3 * ... * n, représentée par la fonction fact(n). On peut voir :

fait(n) = n ! = 1 * 2 * 3 * ... * (n-1) * n = (n-1) !

Ainsi, fact(n) peut être exprimé sous la forme n * fact(n-1), et seul n=1 nécessite un traitement spécial. Donc, le fait(n) écrit de manière récursive est :

Ce qui précède est une fonction récursive. Vous pouvez essayer :

def fact(n):
if n==1:
　　return 1
return n * fact(n - 1)

Si nous calculons fact(5), vous pouvez voir le processus de calcul comme suit selon la définition de la fonction :

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

L'avantage des fonctions récursives est qu'ils sont simples dans leur définition et clairs dans leur logique. Théoriquement, toutes les fonctions récursives peuvent être écrites sous forme de

boucle

, mais la logique des boucles n'est pas aussi claire que la récursivité.

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

Veillez à éviter le débordement de pile lorsque vous utilisez des fonctions récursives. Dans les ordinateurs, les appels de fonction sont implémentés via la structure de données de la pile Chaque fois qu'un appel de fonction est saisi, un cadre de pile est ajouté à la pile. Chaque fois qu'une fonction revient, un cadre de pile est soustrait de la pile. Puisque la taille de la pile n’est pas infinie, trop d’appels récursifs entraîneront un débordement de pile. Vous pouvez essayer de calculer le fait (10 000).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!