Exemple d'analyse de la définition et de l'utilisation des fonctions récursives Python-Tutoriel Python-php.cn

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

黄舟

Libérer： 2017-06-04 10:12:41

original

1657 Les gens l'ont consulté

Cet article présente principalement la définition et l'utilisation de Python fonction 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)

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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!