
# Corrigé du TD Récursivité

## 1. Application du cours

### 1.1 Fonction somme

#### Code de la fonction :
```python
def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)
```

#### Question 1 :
**Combien d'appels de fonction sont nécessaires pour `somme(5)` ? `somme(n)` ?**

- Pour `somme(5)` :
  - La fonction appelle `somme(4)`, puis `somme(3)`, etc., jusqu'à atteindre le cas de base `somme(0)`.
  - Il y a donc 6 appels de fonction au total : `somme(5)`, `somme(4)`, `somme(3)`, `somme(2)`, `somme(1)`, et enfin `somme(0)`.

- Pour `somme(n)` :
  - Le nombre d'appels de fonction est toujours de **n + 1**, car on part de `somme(n)` jusqu'à atteindre le cas de base `somme(0)`.

### 1.2 Fonction factorielle

#### Code de la fonction :
```python
def factorielle(n):
    if n == 0:
        return 1
    else:
        return n * factorielle(n - 1)
```

#### Question 2 :
**Quels seront les appels effectués pour obtenir `factorielle(4)` ?**

Pour calculer `factorielle(4)`, voici les appels récursifs effectués :
1. `factorielle(4)` appelle `factorielle(3)`
2. `factorielle(3)` appelle `factorielle(2)`
3. `factorielle(2)` appelle `factorielle(1)`
4. `factorielle(1)` appelle `factorielle(0)`
5. `factorielle(0)` retourne 1 (cas de base)

La récursion se termine alors et les valeurs remontent :
- `factorielle(1)` retourne `1 * 1 = 1`
- `factorielle(2)` retourne `2 * 1 = 2`
- `factorielle(3)` retourne `3 * 2 = 6`
- `factorielle(4)` retourne `4 * 6 = 24`

## 2. TD

### 2.1 Fonction mystère

#### Code de la fonction :
```python
def mystere(i, k):
    if i <= k:
        print(i)
        mystere(i + 1, k)
```

#### Question :
**Que fait la fonction mystère ?**

La fonction `mystere(i, k)` affiche tous les entiers de `i` à `k` inclus, un par un, en utilisant la récursivité. À chaque appel, elle incrémente `i` de 1 et réimprime jusqu'à ce que `i` dépasse `k`.

Exemple : `mystere(3, 6)` affichera :
```
3
4
5
6
```

### 2.2 Nombre de chiffres d'un nombre

#### Code de la fonction :
```python
def nb_chiffre(n):
    if n < 10:
        return 1
    else:
        return 1 + nb_chiffre(n // 10)
```

#### Explication :
La fonction `nb_chiffre(n)` calcule récursivement le nombre de chiffres d'un nombre `n`. Si `n` est inférieur à 10, il n'a qu'un chiffre, donc elle retourne 1. Sinon, elle divise le nombre par 10 (éliminant ainsi le dernier chiffre) et ajoute 1 au résultat de l'appel récursif.

Exemples :
```python
>>> nb_chiffre(9)
1
>>> nb_chiffre(99)
2
>>> nb_chiffre(1000)
4
```

### 2.3 Maximum d'un tableau

#### Code de la fonction :
```python
def maximum(t):
    if len(t) == 1:
        return t[0]
    else:
        return max(t[0], maximum(t[1:]))
```

#### Explication :
La fonction `maximum(t)` utilise la récursivité pour trouver le plus grand élément d'un tableau. Si le tableau ne contient qu'un seul élément, cet élément est le maximum. Sinon, la fonction compare le premier élément du tableau avec le maximum du reste du tableau (via la tranche `t[1:]`), et retourne le plus grand des deux.

Exemple :
```python
>>> maximum([3, 1, 4, 1, 5, 9])
9
```

## 3. Bonus

### 3.1 Suite de Syracuse

#### Code de la fonction :
```python
def syracuse(u):
    print(u)
    if u > 1:
        if u % 2 == 0:
            syracuse(u // 2)
        else:
            syracuse(3 * u + 1)
```

#### Explication :
La fonction `syracuse(u)` génère et affiche les termes de la suite de Syracuse pour une valeur initiale `u`. Si `u` est pair, elle divise `u` par 2. Si `u` est impair, elle calcule `3 * u + 1`. La fonction continue de s'exécuter jusqu'à ce que `u` soit inférieur ou égal à 1.

Exemple :
```python
>>> syracuse(7)
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1
```
