Ajout de la semaine des cours du 3 au 7 mars

1 files changed, 45 insertions, 0 deletions

diff --git a/semestre 2/informatique/6- Récursion.md b/semestre 2/informatique/6- Récursion.md
new file mode 100644
index 0000000..7ce5af6
--- /dev/null
+++ b/semestre 2/informatique/6- Récursion.md
@@ -0,0 +1,45 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 2
+---
+Une fonction récursive est une fonction qui s'appelle elle-même, e.g.
+```c
+int somme(int n){
+	if (n == 0) return 0;
+	return somme(n-1) + n;
+}
+```
+
+Besoin d'avoir une hypothèse de récurrence quand on fait une récursion
+|> besoin d'avoir une convergence, sinon la récursion est infinie
+
+| Indice           | =   | valeur                 |
+| ---------------- | --- | ---------------------- |
+| (1) somme_int(3) | =   | 3+somme_int(2)         |
+| (2)              | =   | 3+(2+somme_int(1))     |
+| (3)              | =   | 3+(2+(1+somme_int(0))) |
+| (4)              | =   | 3+(2+(1+0))            |
+| (5)              | =   | 6                      |
+La pile ressemble à la même chose que le tableau
+
+Si l'appel est trop vénère, alors il remplit la mémoire et provoque une erreur
+
+Autre exemple :
+```c
+int factoriel(int n){
+	if (n <= 1) return 1;
+	return factoriel(n-1) * n;
+}
+```
+
+La suite de Fibonacci,
+$$ F_n=\left\{\begin{matrix}1&\text{si $n=0$ ou $n=1$}\\F_{n-1}+F_{n-2}&\text{sinon}\end{matrix}\right. $$
+sert à faire une dichotomie plus rapide en pratique (mais pas en théorie)
+```c
+int fibonacci(int n){
+	if (n <= 1) return 1
+	return fibonacci(n-1)+fibonacci(n-2)
+}
+```
\ No newline at end of file