Рекурсія
Функція викликає сама себе для вирішення менших підзадач.
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["Рекурсія"]:::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;
🧠 Перевірка знань
🧒 Простими словами
Уяви, що ти хочеш порахувати сходинки. Ти можеш сказати: 'Скільки сходинок? Ну, це 1 плюс скільки сходинок залишилося'. Ти продовжуєш запитувати, поки сходинок не залишиться. Це рекурсія — вирішення великої проблеми шляхом вирішення її менших версій!
🤓 Expert Deep Dive
Оптимізація хвостового виклику (TCO) усуває зростання стеку для хвостово-рекурсивних функцій (вимагається в Scheme). Мемоізація (Memoization) перетворює експоненціальний Фібоначчі O(2^n) в O(n). Стиль передачі продовження (CPS) робить всі виклики хвостовими. Y-комбінатор дозволяє рекурсію в лямбда-численні. Ліміти глибини стеку (Python ~1000) запобігають крэшам.