Lesson 8
Fonctions et récursivité
1. Les fonctions
Rappelons qu'en mathématiques la factorielle d'un nombre n est définie comme
# calculer 3!
res = 1
for i in range(1, 4):
res *= i
print(res)
# calculer 5!
res = 1
for i in range(1, 6):
res *= i
print(res)
Cependant, si nous faisons une erreur dans le code initial, ce code erroné apparaîtra dans tous les endroits où nous avons copié le calcul factoriel. De plus, le code est plus long qu'il ne pourrait l'être. Pour éviter de réécrire la même logique dans les langages de programmation, il existe des fonctions.
Les fonctions sont les sections de code qui sont isolées du reste du programme et exécutées uniquement lorsqu'elles sont appelées. Vous avez déjà rencontré les fonctions sqrt() , len() et print() . Ils ont tous quelque chose en commun: ils peuvent prendre des paramètres (zéro, un ou plusieurs d'entre eux), et ils peuvent renvoyer une valeur (bien qu'ils ne reviennent pas). Par exemple, la fonction sqrt() accepte un paramètre et renvoie une valeur (la racine carrée du nombre donné). La fonction print() peut prendre un certain nombre d'arguments et ne renvoie rien.
Maintenant, nous voulons vous montrer comment écrire une fonction appelée factorial() qui prend un seul paramètre - le nombre, et renvoie une valeur - la factorielle de ce nombre.
def factorial(n):
res = 1
for i in range(1, n + 1):
res *= i
return res
print(factorial(3))
print(factorial(5))
Nous voulons fournir quelques explications. Tout d'abord, le code de la fonction doit être placé au début du programme (avant l'endroit où nous voulons utiliser la fonction factorial() , pour être précis). La première ligne def factorial(n): de cet exemple est une description de notre fonction; le mot factorial est un identifiant (le nom de notre fonction). Juste après l'identifiant, va la liste des paramètres que notre fonction reçoit (entre parenthèses). La liste est constituée d'identifiants séparés par des virgules des paramètres; dans notre cas, la liste est constituée d'un paramètre n . À la fin de la rangée, mettez un deux-points.
Puis va le corps de la fonction. En Python, le corps doit être indenté (par Tab ou quatre espaces, comme toujours). Cette fonction calcule la valeur de n! et le stocke dans la variable res . La dernière ligne de la fonction est return res , qui quitte la fonction et renvoie la valeur de la variable res .
L'instruction return peut apparaître à n'importe quel endroit d'une fonction. Son exécution quitte la fonction et renvoie la valeur spécifiée à l'endroit où la fonction a été appelée. Si la fonction ne renvoie pas de valeur, l'instruction return ne renverra pas réellement de valeur (bien qu'elle puisse toujours être utilisée). Certaines fonctions n'ont pas besoin de retourner des valeurs, et l'instruction return peut être omise pour elles.
Nous aimerions fournir un autre exemple. Voici la fonction max() qui accepte deux nombres et renvoie le maximum d'entre eux (en fait, cette fonction est déjà devenue la partie de la syntaxe Python).
def max(a, b):
if a > b:
return a
else:
return b
print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))
Maintenant vous pouvez écrire une fonction max3() qui prend trois nombres et retourne le maximum d'entre eux.
def max(a, b):
if a > b:
return a
else:
return b
def max3(a, b, c):
return max(max(a, b), c)
print(max3(3, 5, 4))
La fonction intégrée max() dans Python peut accepter différents nombres d'arguments et en renvoyer le maximum. Voici un exemple de comment une telle fonction peut être écrite.
def max(*a):
res = a[0]
for val in a[1:]:
if val > res:
res = val
return res
print(max(3, 5, 4))
a , indiqué par l'astérisque.
2. Variables locales et globales
Dans la fonction, vous pouvez utiliser des variables déclarées quelque part en dehors de celle-ci:
def f():
print(a)
a = 1
f()
Ici la variable a est mise à 1, et la fonction f() affiche cette valeur, en dépit du fait que lorsque nous déclarons la fonction f cette variable n'est pas initialisée. La raison en est, au moment de l' appel de la fonction f() (la dernière chaîne) la variable a a déjà une valeur. C'est pourquoi la fonction f() peut l'afficher.
De telles variables (déclarées en dehors de la fonction mais disponibles dans la fonction) sont appelées globales .
Mais si vous initialisez une variable à l'intérieur de la fonction, vous ne pourrez pas utiliser cette variable en dehors de celle-ci. Par exemple:
def f():
a = 1
f()
print(a)
Nous recevons error NameError: name 'a' is not defined . Ces variables déclarées dans une fonction sont appelées locales . Ils deviennent indisponibles après la sortie de la fonction.
Ce qui est vraiment charmant ici, c'est ce qui se passe si vous changez la valeur d'une variable globale dans une fonction:
def f():
a = 1
print(a)
a = 0
f()
print(a)
Ce programme vous imprimera les chiffres 1 et 0. Malgré le fait que la valeur de la variable a changé à l'intérieur de la fonction, en dehors de la fonction, elle reste la même! Ceci est fait afin de «protéger» les variables globales contre les changements involontaires de fonction. Donc, si une variable est modifiée dans la fonction, la variable devient une variable locale, et sa modification ne changera pas une variable globale avec le même nom.
Plus formellement: l'interpréteur Python considère une variable locale à la fonction, si dans le code de cette fonction il y a au moins une instruction qui modifie la valeur de la variable. Alors cette variable ne peut pas non plus être utilisée avant l'initialisation. Instructions qui modifient la valeur d'une variable - les opérateurs = , += , et l'utilisation de la variable comme une boucle for paramètre. Cependant, même si l'instruction variable-variable n'est jamais exécutée, l'interpréteur ne peut pas la vérifier et la variable est toujours locale. Un exemple:
def f():
print(a)
if False:
a = 0
a = 1
f()
Une erreur se produit: UnboundLocalError: local variable 'a' referenced before assignment . A savoir, dans la fonction f() l'identifiant a devient une variable locale, puisque la fonction contient la commande qui modifie la variable a . L'instruction de modification ne sera jamais exécutée, mais l'interpréteur ne la vérifiera pas. Par conséquent, lorsque vous essayez d'imprimer la variable a , vous faites appel à une variable locale non initialisée.
Si vous voulez qu'une fonction puisse changer une variable, vous devez déclarer cette variable dans la fonction en utilisant le mot-clé global :
def f():
global a
a = 1
print(a)
a = 0
f()
print(a)
Cet exemple affichera la sortie de 1 1, car la variable a est déclarée globale, et sa modification à l'intérieur de la fonction entraîne sa modification globale.
Cependant, il est préférable de ne pas modifier les valeurs des variables globales dans une fonction. Si votre fonction doit changer une variable, laissez-la retourner , et vous choisissez en appelant la fonction d'assigner explicitement une variable à cette valeur. Si vous suivez ces règles, la logique des fonctions fonctionne indépendamment de la logique du code, et ainsi de telles fonctions peuvent être facilement copiées d'un programme à l'autre, en économisant votre temps.
Par exemple, supposons que votre programme calcule la factorielle du nombre donné que vous voulez enregistrer dans la variable f. Voici comment vous ne devriez pas le faire:
def factorial(n):
global f
res = 1
for i in range(2, n + 1):
res *= i
f = res
n = int(input())
factorial(n)
print(f)
# faire d'autres choses avec variable f
C'est l'exemple du mauvais code, car il est difficile d'utiliser une autre fois. Si demain vous avez besoin d'un autre programme pour utiliser la fonction "factorielle", vous ne pourrez pas simplement copier cette fonction d'ici et coller dans votre nouveau programme. Vous devrez vous assurer que ce programme ne contient pas la variable f .
Il est préférable de réécrire cet exemple comme suit:
# début du morceau de code qui peut être copié du programme au programme
def factorial(n):
res = 1
for i in range(2, n + 1):
res *= i
return res
# fin du morceau de code
n = int(input())
f = factorial(n)
print(f)
# faire d'autres choses avec variable f
Il est utile de dire que les fonctions peuvent renvoyer plus d'une valeur. Voici l'exemple de renvoi d'une liste de deux valeurs ou plus:
return [a, b]
Vous pouvez appeler la fonction d'une telle liste et l'utiliser dans plusieurs affectations:
n, m = f(a, b)
3. Récursivité
Comme nous l'avons vu ci-dessus, une fonction peut appeler une autre fonction. Mais les fonctions peuvent aussi s'appeler! Pour l'illustrer, considérons l'exemple de la fonction de calcul factoriel. Il est bien connu que 0! = 1, 1! = 1. Comment calculer la valeur de n! pour grand n? Si nous pouvions calculer la valeur de (n-1) !, alors nous calculons facilement n !, puisque n! = N⋅ (n-1) !. Mais comment calculer (n-1) !? Si nous avons calculé (n-2) !, alors (n-1)! = (N-1) ⋅ (n-2) !. Comment calculer (n-2) !? Si ... En fin de compte, nous arrivons à 0 !, qui est égal à 1. Ainsi, pour calculer la factorielle, nous pouvons utiliser la valeur de la factorielle pour un entier plus petit. Ce calcul peut être fait en utilisant Python:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
La situation lorsque la fonction s'appelle elle-même est appelée récursivité , et une telle fonction est appelée récursive.
Les fonctions récursives sont un mécanisme puissant dans la programmation. Malheureusement, ils ne sont pas toujours efficaces et conduisent souvent à des erreurs. L'erreur la plus fréquente est la récursion infinie , lorsque la chaîne d'appels de fonctions ne se termine jamais (enfin, elle se termine quand vous n'avez plus de mémoire disponible sur votre ordinateur). Un exemple de récursion infinie:
def f():
return f()
Les deux raisons les plus courantes provoquant une récursion infinie: - Condition d'arrêt incorrecte Par exemple, si dans le programme de calcul factoriel on oublie de mettre la vérification
if n == 0, alorsfactorial(0)appellerafactorial(-1), qui appellerafactorial(-2), etc. - Appel récursif avec des paramètres incorrects. Par exemple, si la fonction
factorial(n)appelle la fonctionfactorial(n), nous obtiendrons également une chaîne infinie d'appels.
Par conséquent, lors du codage d'une fonction récursive, il faut d'abord s'assurer qu'elle atteindra ses conditions d'arrêt - pour réfléchir à la fin de la récursion.