Récursivité et complexité algorithmique

Introduction

La récursivité est un concept fondamental en informatique qui permet de résoudre des problèmes en se basant sur des solutions à des sous-problèmes similaires. Comprendre la récursivité et la complexité algorithmique est essentiel pour analyser l'efficacité des algorithmes. Dans ce cours, nous explorerons ces notions à travers des exemples concrets et des applications pratiques, en approfondissant les différentes facettes de la récursivité et de la complexité algorithmique. La maîtrise de ces concepts est cruciale pour le développement d'algorithmes efficaces et pour la préparation aux épreuves du baccalauréat.

1. Qu'est-ce que la récursivité ?

La récursivité est une méthode de résolution de problèmes où une fonction s'appelle elle-même pour traiter des sous-problèmes. Cette approche est souvent utilisée pour des structures de données comme les arbres ou pour des problèmes mathématiques comme le calcul de la factorielle. La récursivité repose sur deux éléments essentiels : la condition d'arrêt et l'appel récursif. La condition d'arrêt est vitale pour éviter les appels infinis et pour garantir que la fonction finisse par retourner une valeur.

1.1 Exemple de la factorielle

La factorielle d'un nombre entier positif n, notée n!, est définie comme suit :

• n! = n × (n - 1)! pour n > 0


• 0! = 1

Voici comment on peut implémenter la factorielle de manière récursive en Python :
```python

def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n - 1)
```
Si on appelle `factorielle(5)`, cela renverra 120 (5 × 4 × 3 × 2 × 1).

#### Mini-exercice : Calcul de la factorielle
Écrivez une fonction récursive pour calculer la factorielle d'un nombre n. Testez votre fonction avec n = 6.

Correction :
```python
print(factorielle(6)) # Cela doit afficher 720
```

1.2 Analyse de la récursivité

La récursivité peut sembler intuitive, mais elle nécessite une bonne compréhension des appels de fonction et de l'état de la pile d'exécution. Chaque appel de fonction crée un nouvel environnement d'exécution, ce qui entraîne une consommation de mémoire proportionnelle à la profondeur de la récursivité. Par exemple, pour `factorielle(5)`, il y a 6 appels (5, 4, 3, 2, 1, 0), chacun occupant de l'espace sur la pile. Dans des cas extrêmes, comme `factorielle(1000)`, cela peut conduire à un débordement de pile si la profondeur de récursion dépasse la limite de la pile de l'environnement d'exécution.

2. Les types de récursivité

Il existe principalement deux types de récursivité : la récursivité directe et la récursivité indirecte. Chacune a ses propres caractéristiques et applications.

2.1 Récursivité directe

C'est le cas où une fonction s'appelle directement elle-même. Par exemple, la fonction de la factorielle vue précédemment est un exemple de récursivité directe. La récursivité directe est souvent plus simple à comprendre et à implémenter.

#### Exemple supplémentaire : Somme des n premiers entiers
Voici une fonction qui calcule la somme des n premiers entiers :
```python

def somme(n):
if n == 0:
return 0
else:
return n + somme(n - 1)
```
En appelant `somme(5)`, le résultat sera 15 (5 + 4 + 3 + 2 + 1 + 0).

#### Mini-exercice : Somme des n premiers entiers
Testez la fonction `somme` avec n = 10.