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.

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.

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.


• Appel récursif : la fonction s'appelle elle-même avec des arguments modifiés.

#### 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)