Fonctions récursives en Python

Introduction

Bienvenue dans le royaume mythique de Pythonesia, un grand empire réputé pour son utilisation avancée de constructions magiques et mathématiques. En tant que chef de la garde royale du royaume, vous êtes chargé de la défense de l'artefact le plus précieux de l'empire : Le Cristal Récursif. Les légendes disent qu'il a été forgé à l'aide d'un code ancien qui boucle sur lui-même pour créer une source d'énergie infinie. Pour mieux comprendre et protéger cet artefact, vous devez maîtriser l'art de la récursion en Python - la même compétence qui a été utilisée pour le créer.

Votre objectif sera d'exploiter le pouvoir de la récursion pour résoudre des problèmes complexes qui ne peuvent pas être facilement résolus par des moyens conventionnels. En le faisant, vous assurerez la sécurité de la richesse et des connaissances de l'empire contre ceux qui cherchent à les abuser. Préparez-vous à entreprendre un voyage à travers le temps et le code, dévoilant les mystères des fonctions récursives.

Skills Graph

Comprendre la récursion

Dans cette étape, vous allez apprendre le concept de base de la récursion et comment l'implémenter en Python. Une fonction récursive est une fonction qui s'appelle elle-même pour résoudre un problème. La clé pour concevoir une fonction récursive est de s'assurer qu'elle a un cas de base, qui est une condition qui arrête la récursion, et un cas récursif, qui est le cas où la fonction s'appelle elle-même.

Commençons par créer une fonction récursive simple qui calcule le factoriel d'un nombre. Le factoriel d'un nombre n est le produit de tous les entiers positifs inférieurs ou égaux à n.

Ouvrez ~/project/factorial.py dans votre éditeur de texte préféré et ajoutez le code suivant :

def factorial(n):
    if n == 0:  ## Cas de base
        return 1
    else:        ## Cas récursif
        return n * factorial(n - 1)

## Exemple d'utilisation
print(factorial(5))

Pour exécuter le code, utilisez la commande suivante :

python3 factorial.py

Le résultat attendu devrait être 120 car 5! = 5 * 4 * 3 * 2 * 1 = 120.

Récursion avec plusieurs cas de base

Ensuite, vous allez apprendre à construire une fonction récursive avec plusieurs cas de base. Créons une fonction fibonacci dans un fichier nommé fibonacci.py, qui calculera la suite de Fibonacci jusqu'au n-ième nombre. La suite de Fibonacci est une série de nombres où chaque nombre est la somme des deux nombres précédents, en commençant par 0 et 1.

Entrez le code suivant dans ~/project/fibonacci.py :

def fibonacci(n):
    if n == 0:  ## Premier cas de base
        return 0
    elif n == 1:  ## Second cas de base
        return 1
    else:         ## Cas récursif
        return fibonacci(n - 1) + fibonacci(n - 2)

## Exemple d'utilisation
print(fibonacci(10))

Exécutez le code avec la commande :

python3 fibonacci.py

La sortie attendue devrait être 55, car c'est le 10e nombre dans la suite de Fibonacci.

Sommaire

Dans ce laboratoire, nous avons approfondi le concept de récursion en Python en l'appliquant à deux suites mathématiques différentes. Le processus de pensée dans la conception a tourné autour de la création d'un scénario captivant qui rend l'apprentissage de la récursion amusant et pertinent. Les tâches ont été structurées, allant d'un cas de base simple des factoriels à un scénario un peu plus complexe avec plusieurs cas de base dans la suite de Fibonacci, afin de garantir une compréhension complète.

À la fin du laboratoire, vous n'avez pas seulement acquis l'habileté à écrire des fonctions récursives, mais vous avez également compris l'importance des cas de base et le fonctionnement des appels récursifs. Vous détenez désormais la clé pour utiliser des algorithmes récursifs pour résoudre des problèmes du monde réel, une compétence aussi précieuse que le mythe Cristal Récursif de Pythonesia lui-même.