# 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

<!--$\operatorname{bézout}(a, b) = \begin{cases}\end{cases}$-->

```ocaml
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
;;
```