Algorithmique : récursivité et complexité

Introduction

L'algorithmique est au cœur de l'informatique et de la résolution de problèmes. Dans ce chapitre, nous allons explorer deux concepts fondamentaux : la récursivité, qui permet de résoudre des problèmes en se basant sur des solutions de sous-problèmes, et la complexité, qui évalue l'efficacité des algorithmes. Comprendre ces notions est essentiel pour développer des compétences en programmation et en résolution de problèmes, des compétences de plus en plus demandées dans le monde moderne. La maîtrise de l'algorithmique est également cruciale dans des domaines variés tels que la science des données, l'intelligence artificielle, et le développement logiciel.

1. La récursivité

La récursivité est une méthode de définition d'une fonction en termes d'elle-même. Cela permet de décomposer un problème complexe en problèmes plus simples, facilitant ainsi leur résolution. La récursivité est souvent utilisée dans des algorithmes classiques, tels que le tri, la recherche, et le calcul de structures mathématiques.

1.1 Définition d'une fonction récursive

Une fonction récursive se compose généralement de deux parties :

• Cas de base : la condition d'arrêt qui permet de terminer la récursion. Cela est essentiel pour éviter une boucle infinie.


• Appel récursif : la fonction s'appelle elle-même avec des arguments modifiés, ce qui permet de réduire progressivement la taille du problème.

#### Exemple : Factorielle
La factorielle d'un entier n (notée n!) est définie comme :

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


• 0! = 1 (cas de base)

Voici une implémentation en pseudo-code :
```pseudo
fonction factorielle(n)
si n == 0 alors
retourner 1
sinon
retourner n × factorielle(n - 1)
fin fonction
```
Pour n = 5, les appels récursifs se déroulent comme suit :

• factorielle(5)


• 5 × factorielle(4)


• 5 × 4 × factorielle(3)


• 5 × 4 × 3 × factorielle(2)


• 5 × 4 × 3 × 2 × factorielle(1)


• 5 × 4 × 3 × 2 × 1 × factorielle(0)


• 5 × 4 × 3 × 2 × 1 × 1 = 120

#### Mini-exercice : Calcul de la factorielle
Calculez la factorielle de 6 en utilisant la fonction récursive définie ci-dessus.
Correction :
factorielle(6) = 6 × factorielle(5) = 6 × 120 = 720.

1.2 Autres exemples de récursivité

#### Exemple : Calcul de la puissance
La puissance d'un nombre a élevé à n (notée a^n) peut également être définie de manière récursive :

• a^n = a × a^(n - 1) pour n > 0


• a^0 = 1 (cas de base)

Voici un exemple en pseudo-code :
```pseudo
fonction puissance(a, n)
si n == 0 alors
retourner 1
sinon
retourner a × puissance(a, n - 1)
fin fonction