Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 27/03/2024 14:00:00
Submission limit No limitation

Sign in

Sign in

[TP06] Récursion et itération

Jusqu’à présent, nous avons vu comment utiliser des boucles pour résoudre des problèmes itératifs. À présent, nous allons utiliser un autre type de construction, à la fois puissant et élégant : la récursion.

Considérons un exemple pour comprendre la récursion. Une fonction est dite récursive si elle s'appelle elle-même. Ce mécanisme un peu étrange permet souvent de simplifier des processus itératifs. L'analyse des fonctions compute et compute_rec servira à illustrer le lien entre ces deux types d'approches.

Le but de ces deux fonctions est de calculer la somme des entiers de 0 à n. Si l'on devait calculer cela à la main, on développerait sans doute la formule suivante :

\begin{align*} f(n) = \sum_{i=0}^n i &= (0 + 1) + 2 + 3 + ... + n &\quad\quad (1)\\ &= (1 + 2) + 3 + ... + n &\quad\quad (2)\\ &= (3 + 3) + ... + n &\quad\quad (3)\\ &= 6 + ... + n &\quad\quad (4)\\ &= ... &\quad\quad (5)\\ \end{align*}

Cela correspond à la fonction compute(n) qui calcule la somme de façon itérative avec une boucle. Si l'on regroupe les termes de l'équation (1) dans l'autre sens, on peut mettre en évidence une autre façon de définir la fonction f(n) :

\begin{align*} f(n) = n + \boxed{ (n-1) + \boxed{ (n - 2) + \boxed{ (n-3) + ... + \boxed{ 0 }_{f(0)} }_{f(n-3)} }_{f(n-2)} }_{f(n-1)} & \quad \quad (6)\\ \end{align*}

À partir de l'équation (6), on déduit la définition par équations de récurrence de la fonction f(n) :

\begin{align*} f(0) &= 0 & &\quad\quad (7)\\ f(n) &= n + f(n-1) &\quad \quad \forall n > 0 &\quad\quad (8)\\ \end{align*}

L'équation (7) définit le cas de base. L'équation (8) définit tous les autres cas par récurrence. C'est-à-dire que la fonction f(n) est définie à partir de cette même fonction, mais avec un argument différent de n (ici n-1). Le cas de base est très important : sans celui-ci, (8) ne s'arrête jamais ou n'est pas défini pour n=0. Ce principe est utilisé pour définir la fonction récursive compute_rec(n).

Question 1: Somme des n premiers entiers

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

  1. le cas de base,
  2. comment traiter le cas de base,
  3. comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier sum_rec.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def compute_rec(n):
    """
    Approche récursive
    pre: `n` est un entier >= 0
    post: retourne la somme des entiers de 0 à `n` compris
    """
Question 2: Nombre d'appels récursifs

Combien y a-t-il d'appels récursifs si n = 7 ?

Question 3: Complexité temporelle

Intuitivement, quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.