DataTerminology.comNEW
A technique where a function solves problems by calling itself on smaller instances until reaching base cases.
DESCRIPTION
Recursion expresses solutions by reducing a problem to simpler subproblems of the same form, typically with a base case to stop further calls. It is fundamental in functional programming, tree and graph algorithms, and mathematical definitions via induction. While elegant, recursion can cause deep call stacks and performance issues if not carefully designed or optimized with tail recursion and memoization. Many languages support recursion natively, with limits to prevent infinite regress.
ALTERNATIVE DEFINITIONS
Wikipedia
Recursion occurs when a thing is defined in terms of itself or of its type.
Generalizes recursion beyond code to mathematics and definitions.
MDN Web Docs
Recursion is a programming technique in which a function calls itself to solve a problem.
Emphasizes programming technique and self-calls.
MIT OpenCourseWare
Recursion is a method of solving problems where the solution depends on solutions to smaller instances of the same problem.
Highlights dependency on smaller subproblem solutions.
RELATED TERMS
Divide and Conquer Call Stack Tail Recursion Dynamic Programming Induction Stack Overflow Functional Programming Tree Traversal
COMPETING TERMS
KNOWLEDGE AREAS
Programming Languages Mathematics Software Engineering Data Science
TARGET AUDIENCE
Software Developer Data Scientist AI Engineer Software Architect
EXTERNAL SOURCES
- Wikipedia - Recursion
- MDN Web Docs - Concise programming glossary entry
- Python Docs - Recursion limits and stack behavior
- MIT OpenCourseWare - Course materials on recursion
TOP QUESTIONS
Why use Recursion instead of iteration?
Recursion can express solutions more naturally for hierarchical structures like trees. It simplifies code at the cost of stack overhead.
Category: Opinion
What is a base case in Recursion?
It’s a condition that stops further self-calls, returning a direct result. Without base cases, recursion leads to infinite loops.
Category: Requirements
How to optimize Recursion?
Use tail recursion where supported, memoization for overlapping subproblems, or convert to iteration to avoid deep stacks.
Category: Best practices
What problems suit Recursion well?
Tree traversals, divide-and-conquer algorithms, parsing, and dynamic programming formulations often benefit from recursion.
Category: Example
What is the risk of deep Recursion?
Stack overflow and performance degradation can occur. Monitor recursion depth or refactor to iterative solutions.
Category: Risks
Is Recursion important in functional programming?
Yes. Recursion often replaces loops, and languages may optimize tail calls for performance.
Category: Relevancy
How does Recursion relate to mathematical induction?
Recursive definitions parallel inductive proofs: base cases and step rules define behavior for all inputs.
Category: Example
What is mutual Recursion?
Two or more functions call each other. It’s useful in state machines and parsers but can be hard to reason about.
Category: Overview
When should Recursion be avoided?
Avoid when stack limits are tight or performance critical paths need predictable memory and tail-call optimization isn’t available.
Category: Mistakes