From 4a3afaf44aa29e66a6c879c60322015a2920a5ab Mon Sep 17 00:00:00 2001
From: Anhgelus Morhtuuzh <anhgelus@anhgelus.world>
Date: Mon, 10 Mar 2025 10:31:33 +0100
Subject: Ajout de la semaine des cours du 3 au 7 mars

---
 "semestre 2/informatique/6- R\303\251cursion.md" | 45 ++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 "semestre 2/informatique/6- R\303\251cursion.md"

(limited to 'semestre 2/informatique/6- Récursion.md')

diff --git "a/semestre 2/informatique/6- R\303\251cursion.md" "b/semestre 2/informatique/6- R\303\251cursion.md"
new file mode 100644
index 0000000..7ce5af6
--- /dev/null
+++ "b/semestre 2/informatique/6- R\303\251cursion.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
-- 
cgit v1.2.3