Récursion
Fonction s'appelant elle-même pour résoudre des sous-problèmes plus petits.
Recursion is a programming technique where a function calls itself directly or indirectly. It involves a 'base case' to terminate the process and a 'recursive step' that breaks the problem into a simpler version of itself. It is particularly elegant for solving problems involving trees, fractals, and mathematical sequences.
graph LR
Center["Récursion"]:::main
Rel_algorithm["algorithm"]:::related -.-> Center
click Rel_algorithm "/terms/algorithm"
Rel_adiabatic_quantum_computation["adiabatic-quantum-computation"]:::related -.-> Center
click Rel_adiabatic_quantum_computation "/terms/adiabatic-quantum-computation"
Rel_search_algorithm["search-algorithm"]:::related -.-> Center
click Rel_search_algorithm "/terms/search-algorithm"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Test de connaissances
🧒 Explique-moi comme si j'avais 5 ans
Imaginez que vous voulez compter les marches. Vous pourriez dire : 'Combien de marches ? Eh bien, c'est 1 plus combien de marches il reste'. Vous continuez à demander jusqu'à ce qu'il n'y ait plus de marches. C'est la récursivité !
🤓 Expert Deep Dive
L'optimisation des appels terminaux (TCO) élimine la croissance de la pile. La mémoïsation transforme Fibonacci exponentiel en linéaire. Le style de passage de continuation (CPS) rend tous les appels terminaux. Le combinateur Y permet la récursivité dans le lambda-calcul.