---
title: "Récursivité et représentation des nombres"
date: "2024-10-29"
---

# La récursivité

\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;
}
```

# Exponentiation rapide

\Huge L'exponentiation rapide ou indienne

# Exponentiation rapide ou indienne (1/4)

## But: Calculer $x^n$

* Quel est l'algorithmie le plus simple que vous pouvez imaginer?

. . .

```C
double pow(double x, int n) {
    if (0 == n) {
        return 1;
    }
    double p = x;
    for (int i = 1; i < n; ++i) {
        p = p * x; // p *= x
    }
    return p;
}
```

* Combien de multiplication et d'assignations en fonction de `n`?

. . .

* `n` assignations et `n` multiplications.

# Exponentiation rapide ou indienne (2/4)

* Proposez un algorithme naïf et récursif

. . .

```C
double pow(double x, int n) {
    if (n != 0) {
        return x * pow(x, n-1);
    } else {
        return 1;
    }
}
```

# Exponentiation rapide ou indienne (3/4)

## Exponentiation rapide ou indienne de $x^n$

* Écrivons $n=\sum_{i=0}^{d-1}b_i 2^i,\ b_i=\{0,1\}$ (écriture binaire sur $d$ bits, avec
$d\sim\log_2(n)$).
* 
$$
x^n={x^{2^0}}^{b_0}\cdot {x^{2^1}}^{b_1}\cdots {x^{2^{d-1}}}^{b_{d-1}}.
$$
* On a besoin de $d$ calculs pour les $x^{2^i}$.
* On a besoin de $d$ calculs pour évaluer les produits de tous les termes.

## Combien de calculs en terme de $n$?

. . .

* $n$ est représenté en binaire avec $d$ bits $\Rightarrow d\sim\log_2(n)$.
* il y a $2\log_2(n)\sim \log_2(n)$ calculs.

# Exponentiation rapide ou indienne (4/4)

## Le vrai algorithme

* Si n est pair: calculer $\left(x^{n/2}\cdot x^{n/2}\right)$,
* Si n est impair: calculer $x \cdot \left(x^{(n-1)/2}\right)^2=x\cdot x^{n-1}$.

## Exercice: écrire l'algorithme récursif correspondant

. . .

```C
double pow(double x, int n) {
    if (0 == n) {
        return 1;
    } else if (n % 2 == 0) {
        return pow(x, n / 2) * pow(x, n/2);
    } else {
        return x * pow(x, (n-1));
    }
}
```


