L'algorithme récursif Python est-il difficile ? Exemples détaillés de fonctions récursives Python-Tutoriel Python-php.cn

L'algorithme récursif Python est-il difficile ? Exemples détaillés de fonctions récursives Python

Tomorin

Libérer： 2018-08-17 17:53:32

original

2479 Les gens l'ont consulté

Au sein d'une fonction, d'autres fonctions peuvent être appelées. Si une fonction s'appelle en interne, la fonction est une fonction récursive.

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

fact(n). ) = n ! = 1 x 2 x 3 x ... x (n-1) x n = (n-1) ! x n = fait(n-1) x n

Donc, fait(n) peut être exprimé Pour n x fact(n-1), seul n=1 nécessite un traitement spécial.

Ainsi, fact(n) est écrit de manière récursive comme :

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

Copier après la connexion

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

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
933262154439441526816992388562667004907159682643816214685
92963895217599993229915608941463976156518286253697920827223
758251185210916864000000000000000000000000

Copier après la connexion

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

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

Les avantages des fonctions récursives sont une définition simple et une logique claire. Théoriquement, toutes les fonctions récursives peuvent être écrites dans une boucle, mais la logique des boucles n'est pas aussi claire que la récursivité.

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 fact(1000) :

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison

Copier après la connexion

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!