DS Récursivité

Dans toutes les questions où il est demandé d’écrire du code, on attendra, sauf mention contraire :

  • Des assertions pour vérifier les préconditions de valeur (on ne s’occupe pas des types)

  • Une docstring pour chaque fonction. Une attention particulière sera portée pour celles des fonctions non définies dans le sujet

  • Des tests pour chaque fonction

  • La complexité des fonctions, en \(O\)

Exercice 1 : Cours

Dans cet exercice, on cherche à créer une fonction qui calcule la somme de \(1\) à \(n\).

On note donc \(S_n=\underset{1\leq i\leq n}{\Sigma}i=1+2+...n\) pour \(n > 0\) et \(S_0=0\)

Question

Écrire avec un for ou while la fonction somme telle que :

  • L'entrée est \(n\) un entier positif

  • La sortie est \(S_n\)

Solution

1
def somme(n):
2
    """
3
    Entrée : n, un entier positif
4
    Sortie : la somme des n premiers entiers positifs
5
    """
6
    assert n >= 0, "n doit être positif ou nul"
7
    sn = 0
8
    for i in range(n+1):
9
        sn += i
10
    return sn
11
12
assert somme(0) == 0
13
assert somme(1) == 1
14
assert somme(10) == 55
15
try:
16
    somme(-1)
17
    assert False, "somme(-1) devrait échouer"
18
except AssertionError:
19
    pass
20
except e:
21
    raise e
22
    
La fonction ne comporte qu'une boucle for dont chaque étape est en temps constant.
La boucle est effectuée \(O(n)\) fois.
La complexité est donc \(O(n)\).
Question
Écrire la version récursive de la fonction somme_rec telle que :
  • L'entrée est \(n\) un entier positif
  • La sortie est \(S_n\)
Solution
1
def somme_rec(n):
2
    """
3
    Entrée : n, un entier positif
4
    Sortie : la somme des n premiers entiers positifs
5
    """
6
    assert n >= 0, "n doit être positif ou nul"
7
    if n == 0:
8
        return 0
9
    return n + somme_rec(n-1)
10
11
assert somme_rec(0) == 0
12
assert somme_rec(1) == 1
13
assert somme_rec(10) == 55
14
try:
15
    somme_rec(-1)
16
    assert False, "somme_rec(-1) devrait échouer"
17
except AssertionError:
18
    pass
19
except e:
20
    raise e
Chaque appel de la fonction déclenche au plus 1 appel récursif, et le corps est en temps constant.
On décrémente \(n\) de \(1\) à chaque appel. On fait \(O(n)\) appels récursifs.
La complexité est donc \(O(n)\).
Question
Donner les trois conditions suffisantes de terminaison des fonctions récursives.
Expliciter pourquoi l'algorithme de la question précédente les respectent.
Solution
Les conditions suffisantes de terminaison des fonctions récursives sont :
  1. Condition d'arrêt : Il y a une condition d'arrêt ;
  2. Variant : Il y a un variant strictement décroissant, à chaque appel récursif ;
  3. Condition d'arrêt atteinte : Le variant atteint toujours la condition d'arrêt.
Dans la question précédente, elles sont atteintes car :
  1. Conditions d'arrêt : Si \(n\) est nul, on ne fait plus d'appels récursifs et on retourne ;
  2. Variant : À chaque appel, \(n\) est décrémenté de 1, donc strictement décroissant ;
  3. Condition d'arrêt atteinte : Si \(n\) est positif ou nul, alors il décroît de 1 à chaque appel et donc atteint 0. S'il est négatif, l'assert échoue et donc termine.