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.
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.
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).
2. Les types de récursivité
Il existe principalement deux types de récursivité : la récursivité directe et la récursivité indirecte.
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.
2.2 Récursivité indirecte
C'est le cas où une fonction A appelle une fonction B, qui à son tour appelle la fonction A. Un exemple simple serait :