---
title: "Récursivité"
date: "2023-10-31"
---

# Nombres à virgule (1/3)

## Comment manipuler des nombres à virgule?

$$
0.1 + 0.2 = 0.3.
$$

Facile non?

. . .

## Et ça?

```C
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    float a = atof(argv[1]);
    float b = atof(argv[2]);
    printf("%.10f\n", (double)(a + b));
}
```

. . .

## Que se passe-t-il donc?

# Nombres à virgule (2/3)

## Nombres à virgule fixe

+-------+-------+-------+-------+-----+----------+----------+----------+----------+
| $2^3$ | $2^2$ | $2^1$ | $2^0$ | `.` | $2^{-1}$ | $2^{-2}$ | $2^{-3}$ | $2^{-4}$ |
+-------+-------+-------+-------+-----+----------+----------+----------+----------+
| `1`   | `0`   | `1`   |  `0`  | `.` | `0`      | `1`      | `0`      | `1`      |
+-------+-------+-------+-------+-----+----------+----------+----------+----------+

## Qu'est-ce ça donne en décimal?

. . .

$$
2^3+2^1+\frac{1}{2^2}+\frac{1}{2^4} = 8+2+0.5+0.0625=10.5625.
$$

## Limites de cette représentation? 

. . .


* Tous les nombres `> 16`.
* Tous les nombres `< 0.0625`.
* Tous les nombres dont la décimale est pas un multiple de `0.0625`.

# Nombres à virgule (3/3)

## Nombres à virgule fixe

* Nombres de $0=0000.0000$ à $15.9375=1111.1111$.
* Beaucoup de "trous" (au moins $0.0625$) entre deux nombres.

## Solution partielle?

. . .

* Rajouter des bits.
* Bouger la virgule.

# Nombres à virgule flottante (1/2)

## Notation scientifique

* Les nombres sont représentés en terme:
    * Une mantisse
    * Une base
    * Un exposant

$$
\underbrace{22.1214}_{\mbox{nombre}}=\underbrace{221214}_{\mbox{mantisse}}\cdot
{\underbrace{10}_{\mbox{base}}}{\overbrace{^{-4}}^{\mbox{exp.}}},
$$

. . .

On peut donc séparer la représentation en 2:

* La mantisse
* L'exposant

# Nombres à virgule flottante (2/2)

## Quel est l'avantage?

. . .

On peut représenter des nombres sur énormément d'ordres de grandeur avec un
nombre de bits fixés.

## Différence fondamentale avec la virgule fixe?

. . .

La précision des nombres est **variable**:

* On a uniquement un nombre de chiffres **significatifs**.
$$
123456\cdot 10^{23}+ 123456\cdot 10^{-23}.
$$

## Quel inconvénient y a-t-il?

. . .

Ce mélange d'échelles entraîne un **perte de précision**.

# Nombres à virgule flottante simple précision (1/4)

Aussi appelés *IEEE 754 single-precision binary floating point*.

![Nombres à virgule flottante 32 bits. Source:
[Wikipedia](https://en.wikipedia.org/wiki/Single-precision_floating-point_format)](figs/Float_example_bare.svg)

## Spécification

* 1 bit de signe,
* 8 bits d'exposant,
* 23 bits de mantisse.

$$
(-1)^{b_{31}}\cdot 2^{(b_{30}b_{29}\dots b_{23})_{2}-127}\cdot (1.b_{22}b_{21}\dots b_{0})_{2},
$$

## Calculer la valeur décimale du nombre ci-dessus

# Nombres à virgule flottante simple précision (2/4)

![Un exercice de nombres à virgule flottante 32 bits. Source:
[Wikipedia](https://en.wikipedia.org/wiki/Single-precision_floating-point_format)](figs/Float_example.svg)

. . .

\begin{align}
\mbox{exposant}&=\sum_{i=0}^7 b_{23+i}2^i=2^2+2^3+2^4+2^5+2^6=124-127,\\
\mbox{mantisse}&=1+\sum_{i=1}^{23}b_{23-i}2^{-i}=1+2^{-2}=1.25,\\
&\Rightarrow (-1)^0\cdot 2^{-3}\cdot 1.25=0.15625
\end{align}

# Nombres à virgule flottante simple précision (3/4)

## Quel nombre ne peux pas être vraiment représenté?

. . .

## Zéro: exception pour l'exposant

* Si l'exposant est `00000000` (zéro)
$$
(-1)^{\mbox{sign}}\cdot 2^{-126}\cdot 0.\mbox{mantisse},
$$
* Sinon si l'exposant est `00000001` à `11111110`
$$
\mbox{valeur normale},
$$
* Sinon `11111111` donne `NaN`.

# Nombres à virgule flottante simple précision (4/4)

## Quels sont les plus petits/grands nombres positifs représentables?

. . .

\begin{align}
0\ 0\dots0\ 0\dots01&=2^{-126}\cdot 2^{-23}=1.4...\cdot
10^{-45},\\
0\ 1\dots10\ 1\dots1&=2^{127}\cdot (2-2^{-23})=3.4...\cdot
10^{38}.
\end{align}

## Combien de chiffres significatifs en décimal?

. . .

* 24 bits ($23 + 1$) sont utiles pour la mantisse, soit $2^{24}-1$:
    * La mantisse fait $\sim2^{24}\sim 10^7$,
    * Ou encore $\sim \log_{10}(2^{24})\sim 7$.
* Environ **sept** chiffres significatifs.

# Nombres à virgule flottante double précision (64bits)

## Spécification

* 1 bit de signe,
* 11 bits d'exposant,
* 52 bits de mantisse.

. . .

## Combien de chiffres significatifs?

* La mantisse fait $\sim 2^{53}\sim10^{16}$,
* Ou encore $\sim \log_{10}(2^{53})\sim 16$,
* Environ **seize** chiffres significatifs.

## Plus petit/plus grand nombre représentable?

. . .

* Plus petite mantisse et exposant: $\sim 2^{-52}\cdot 2^{-1022}\sim 4\cdot 10^{-324}$,
* Plus grande mantisse et exposant: $\sim 2\cdot 2^{1023}\sim \cdot 1.8\cdot 10^{308}$.

# Précision finie (1/3)

## Erreur de représentation

* Les nombres réels ont potentiellement un **nombre infini** de décimales
    * $1/3=0.\overline{3}$,
    * $\pi=3.1415926535...$.
* Les nombres à virgule flottante peuvent en représenter qu'un **nombre
  fini**.
  * $1/3\cong 0.33333$, erreur $0.00000\overline{3}$.
  * $\pi\cong3.14159$, erreur $0.0000026535...$.

On rencontre donc des **erreurs de représentation** ou **erreurs
d'arrondi**.

. . .
    
## Et quand on calcule?

* Avec deux chiffres significatifs
\begin{align}
&8.9+(0.02+0.04)=8.96=9.0,\\
&(8.9+0.02)+0.04=8.9+0.04=8.9.
\end{align}

. . .

## Même pas associatif!

# Précision finie (2/3)

## Erreur de représentation virgule flottante

$$
(1.2)_{10} = 1.\overline{0011}\cdot 2^0\Rightarrow 0\ 01111111\
00110011001100110011010.
$$
Erreur d'arrondi dans les deux derniers bits et tout ceux qui viennent
ensuite
$$
\varepsilon_2 = (00000000000000000000011)_2.
$$
Ou en décimal
$$
\varepsilon_{10} = 4.76837158203125\cdot 10^{-8}.
$$

# Précision finie (3/3)

## Comment définir l'égalité de 2 nombres à virgule flottante?

. . .

Ou en d'autres termes, pour quel $\varepsilon>0$ (appelé `epsilon-machine`) on a
$$
1+\varepsilon = 1,
$$
pour un nombre à virgule flottante?

. . .

Pour un `float` (32 bits) la différence est à 
$$
2^{-23}=1.19\cdot 10^{-7},
$$
Soit la précision de la mantisse.

## Comment le mesurer (par groupe)?

. . .

```C
float eps = 1.0;
while ((float)1.0 + (float)0.5 * eps != (float)1.0) {
    eps = (float)0.5 * eps;
}
printf("eps = %g\n", eps);
```

# Erreurs d'arrondi

Et jusqu'ici on a encore pas fait d'arithmétique!

## Multiplication avec deux chiffres significatifs, décimal

$$
(1.1)_{10}\cdot (1.1)_{10}=(1.21)_{10}=(1.2)_{10}.
$$
En continuant ce petit jeu:
$$
\underbrace{1.1\cdot 1.1\cdots 1.1}_{\mbox{10 fois}}=2.0.
$$
Alors qu'en réalité
$$
1.1^{10}=2.5937...
$$
Soit une erreur de près de 1/5e!

. . .

## Le même phénomène se produit (à plus petite échelle) avec les `float` ou `double`.

# And now for something completely different

\Huge La récursivité

# La factorielle: Code impératif

* Code impératif

```C
int factorial(int n) {
    int f = 1;
    for (int i = 1; i < n; ++i) {
        f *= i;
    }
    return f;
}
```

# Exemple de récursivité (1/2)

## La factorielle

```C
int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}
```

. . .

## Que se passe-t-il quand on fait `factorial(4)`?

. . .

## On empile les appels

+----------------+----------------+----------------+----------------+
|                |                |                | `factorial(1)` |
+----------------+----------------+----------------+----------------+
|                |                | `factorial(2)` | `factorial(2)` |
+----------------+----------------+----------------+----------------+
|                | `factorial(3)` | `factorial(3)` | `factorial(3)` |
+----------------+----------------+----------------+----------------+
| `factorial(4)` | `factorial(4)` | `factorial(4)` | `factorial(4)` |
+----------------+----------------+----------------+----------------+

# Exemple de récursivité (2/2)

## La factorielle

```C
int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}
```

. . .

## Que se passe-t-il quand on fait `factorial(4)`?

. . .

## On dépile les calculs

+----------------+----------------+----------------+----------------+
|  `1`           |                |                |                |
+----------------+----------------+----------------+----------------+
| `factorial(2)` |  `2 * 1 = 2`   |                |                |
+----------------+----------------+----------------+----------------+
| `factorial(3)` | `factorial(3)` |  `3 * 2 = 6`   |                |
+----------------+----------------+----------------+----------------+
| `factorial(4)` | `factorial(4)` | `factorial(4)` |  `4 * 6 = 24`  |
+----------------+----------------+----------------+----------------+

# La récursivité (1/4)

## Formellement 

* Une condition de récursivité - qui *réduit* les cas successifs vers...
* Une condition d'arrêt - qui retourne un résultat

## Pour la factorielle, qui est qui?

```C
int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}
```

# La récursivité (2/4)

## Formellement 

* Une condition de récursivité - qui *réduit* les cas successifs vers...
* Une condition d'arrêt - qui retourne un résultat

## Pour la factorielle, qui est qui?

```C
int factorial(int n) {
    if (n > 1) { // Condition de récursivité
        return n * factorial(n - 1);
    } else {     // Condition d'arrêt
        return 1;
    }
}
```

# La récursivité (3/4)

## Exercice: trouver l'$\varepsilon$-machine pour un `double`

. . .

Rappelez-vous vous l'avez fait en style **impératif** plus tôt.

. . .

```C
double epsilon_machine(double eps) {
    if (1.0 + eps != 1.0) {
        return epsilon_machine(eps / 2.0);
    } else {
        return eps;
    }
}
```

# La récursivité (4/4)

\footnotesize

## Exercice: que fait ce code récursif?

```C
void recurse(int n) {
    printf("%d ", n % 2);
    if (n / 2 != 0) {
        recurse(n / 2);
    } else {
        printf("\n");
    }
}
recurse(13); 
```

. . .

```C
recurse(13): n = 13, n % 2 = 1, n / 2 = 6,
    recurse(6): n = 6, n % 2 = 0, n / 2 = 3,
        recurse(3): n = 3, n % 2 = 1, n / 2 = 1,
            recurse(1): n = 1, n % 2 = 1, n / 2 = 0.

// affiche: 1 1 0 1
```

. . .

Affiche la représentation binaire d'un nombre!

# Exercice: réusinage et récursivité (1/4)

## Réusiner le code du PGCD avec une fonction récursive

## Étudier l'exécution

```C
42 = 27 * 1 + 15
27 = 15 * 1 + 12
15 = 12 * 1 + 3
12 = 3  * 4 + 0
```

# Exercice: réusinage et récursivité (2/4)

## Réusiner le code du PGCD avec une fonction récursive

## Étudier l'exécution

```C
42 = 27 * 1 + 15   |   PGCD(42, 27) 
27 = 15 * 1 + 12   |   PGCD(27, 15) 
15 = 12 * 1 +  3   |   PGCD(15, 12) 
12 =  3 * 4 +  0   |   PGCD(12,  3) 
```

# Exercice: réusinage et récursivité (3/4)

## Réusiner le code du PGCD avec une fonction récursive

## Étudier l'exécution

```C
42 = 27 * 1 + 15   |   PGCD(42, 27) 
27 = 15 * 1 + 12   |   PGCD(27, 15) 
15 = 12 * 1 +  3   |   PGCD(15, 12) 
12 =  3 * 4 +  0   |   PGCD(12,  3) 
```

## Effectuer l'empilage - dépilage

. . .

```C
PGCD(12,  3)    |     3
PGCD(15, 12)    |     3
PGCD(27, 15)    |     3
PGCD(42, 27)    |     3
```

# Exercice: réusinage et récursivité (4/4)

## Écrire le code

. . .

```C
int pgcd(int n, int m) {
    if (n % m > 0) {
        return pgcd(m, n % m);
    } else {
        return m;
    }
}
```

# La suite de Fibonacci (1/2)

## Règle

$$
\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2),\quad
\mathrm{Fib}(0)=0,\quad \mathrm{Fib}(1)=1.
$$

## Exercice: écrire la fonction $\mathrm{Fib}$ en récursif et impératif

. . .

## En récursif (6 lignes)

```C
int fib(int n) {
    if (n > 1) {
        return fib(n - 1) + fib(n - 2);
    } 
    return n;
}
```

# La suite de Fibonacci (2/2)

## Et en impératif (11 lignes)

```C
int fib_imp(int n) {
    int fib0 = 1;
    int fib1 = 1;
    int fib  = n == 0 ? 0 : fib1;
    for (int i = 2; i < n; ++i) {
        fib  = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib;
    }
    return fib;
}
```

