Comprendre la récursivité en Python : alors, allez-vous y faire face ?

La récursion est un concept fondamental en programmation, mais elle peut parfois sembler un peu mystérieuse. Alors, simplifions cela et voyons que c'est plus facile qu'il n'y paraît !

Qu’est-ce que la récursivité ?

La récursivité, c'est lorsqu'une fonction résout un problème en s'appelant... elle-même ! Oui, c'est vrai. Cela fonctionne comme une histoire que vous racontez encore et encore, mais un peu plus courte à chaque fois jusqu'à la fin. Mais pour que cela fonctionne correctement, il doit respecter deux règles d'or :

1. Condition de terminaison : c'est le point où la fonction doit s'arrêter, sinon elle restera dans une boucle éternelle (on ne veut pas ça, non ?).
2. Auto-appel : c'est à ce moment-là que la fonction s'appelle elle-même, en allant de plus en plus profondément jusqu'à atteindre la condition de terminaison.

Voyons maintenant comment cela fonctionne en pratique !

Comment ça marche ?

Pour mieux l'expliquer, rien de mieux que l'exemple classique du factorial ! Imaginez que nous voulions calculer (5 !) (lire « factorielle cinq »). Comment ça marche ?

5 ! = 5*4*3*2*1 !

Cependant, avec la récursivité, on peut y penser comme ceci :

5 ! = 5*4 !

Et, dans l'ordre, 4 ! vaut (4 * 3 !), et ainsi de suite, jusqu'à atteindre (1 !), qui est notre cas de base (la terminaison état).

Exemple pratique : factoriel

Passons au code, car c'est là que le concept prend vie ! Voici le fameux calcul factoriel utilisant la récursion :

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

Explication :

1. Le cas de base ici est lorsque le nombre est 0 ou 1, où la fonction renvoie simplement 1.
2. Si le nombre est supérieur à 1, la fonction est appelée avec le numéro - 1, accumulant les valeurs jusqu'au cas de base.

Complexité

• Heure : (O(n)) — puisqu'il y a n appels récursifs.
• Espace : (O(n)) — la profondeur de la pile d'exécution est n.

Exemple pratique : Fibonacci

Un autre exemple largement utilisé est la Séquence de Fibonacci. Elle est comme ça :

f(0) = 0, f(1) = 1, f(n) = f(n - 1) f(n - 2)

Passons au code !

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

Complexité de Fibonacci :

• Temps : (O(2^n)) — exponentiel ! ⚠️
• Espace : (O(n)) — utilisation de la pile pour les appels récursifs.

C'est pourquoi, pour les grandes valeurs, le calcul de Fibonacci avec récursion pure peut s'avérer un peu fastidieux. Mais à des fins d'apprentissage, c'est un excellent exemple !

Enfin

La récursion est un concept clé en programmation et, même si cela peut paraître un peu intimidant au début, cela devient beaucoup plus facile avec la pratique. Ces exemples factoriels et de Fibonacci ne sont qu’un début !

Si vous souhaitez vous entraîner, consultez-le et faites-en une copie, dans ce Colab ici !

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!