recursion
A technique where a function solves a problem by calling itself on a smaller version of the same problem.
In more detail
Every recursive function needs a base case that stops the calls, or it will recurse forever. Each call that has not yet returned occupies a frame on the call stack, so deep recursion uses memory proportional to its depth. Trees, divide and conquer, and backtracking are naturally recursive.
Example
Recursive rendering cannot be paused, so React Fiber replaces it with a loop that follows child, sibling and return pointers.Related terms
- base case — The smallest input a recursive function answers directly, without calling itself again, which stops the recursion.
- call stack — The region of memory where a running program keeps one frame for each function call that has started but not yet returned.
- RecursionError — The Python exception raised when recursion goes deeper than the interpreter's limit, which is 1,000 frames by default.
- iteration — Repeating a block of steps in a loop, as opposed to having a function call itself.
- Fiber — The internal object React keeps for each component instance, and the name of the React 16+ engine built on those objects.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers
- React Fiber Architecture: Work Units, Priority And Commits — React 19 & Modern Component Architecture
- Functions, Return Values And Recursion — PCEP Certified Entry-Level Python Programmer (PCEP-30-02) Exam Prep
- Functions And Exceptions Sprint — PCEP Certified Entry-Level Python Programmer (PCEP-30-02) Exam Prep
- Mock, Review And Exam Day — PCEP Certified Entry-Level Python Programmer (PCEP-30-02) Exam Prep
- Introspection: hasattr, __name__, __module__ And __bases__ — PCAP Certified Associate in Python Programming (PCAP-31-03) Exam Prep
References
- NIST Dictionary of Algorithms and Data Structures: recursion
- Python tutorial: defining functions
- MDN glossary: recursion