mp2i-info/td3/td3.md

Récursivité

Exercice 1

Formules naïves :

• $x\times y = \begin{cases} 0 & \text{si $y=0$}\ x & \text{si $y=1$}\ x + (x \times (y-1)) & \text{si $y>1$} \end{cases}$

• $a^n = \begin{cases} 1 & \text{si $a=0$}\ a\times a^{n-1} & \text{si $n>0$} \end{cases}$

Formules dichotomiques :

• $x\times y = \begin{cases} 0 & \text{si $y=0$}\ x & \text{si $y=1$}\ 2\times (x \times {y \over 2}) & \text{si y>1 et y pair}\ x + 2\times (x \times {y - 1 \over 2}) & \text{si y>1 et y impair} \end{cases}$

• $a^n = \begin{cases} 1 & \text{si $a=0$}\ (a^{n \over 2})^2 & \text{si n>0 et n pair}\ a\times (a^{n-1 \over 2})^2 & \text{si n>0 et n impair} \end{cases}$

Les formules naïves sont de complexité O(y) et O(n) alors que les formules dichotomiques sont de complexité O(\log_2(y)) et O(\log_2(n)), ce qui est plus efficace.

Exercice 2

$\operatorname{pgcd}(a, b) = \begin{cases} \operatorname{pgcd}(b, a) & \text{si $b>a$}\ \operatorname{pgcd}(b, a \mod b) & \text{si $a \mod b > 0$}\ b & \text{si $a \mod b = 0$} \end{cases}$

Exercice 3

let rec bezout a b = match a mod b with
  | 1 -> 1, (a/b)
  | r ->
    let c, d = bezout b r in
    let () = print_int c in
    let () = print_newline () in
    let () = print_int d in
    let () = print_newline () in
    c+(d*r), d
;;