59 lines
1.4 KiB
Markdown
59 lines
1.4 KiB
Markdown
# 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
|
|
;;
|
|
```
|