Section: STEM · Computer ScienceDifficulty: Medium
Recursion
USUK
A programming technique where a function calls itself to solve smaller instances of a problem.
Definition
Recursion is a programming and mathematical technique where a function or algorithm calls itself with a smaller or simpler input to solve a problem, breaking it into subproblems of the same type until reaching a base case. Every recursive algorithm requires at least one base case to prevent infinite loops. Recursion is naturally suited to problems with a recursive structure, such as tree traversal, fractal generation, and divide-and-conquer algorithms.
Example
“Computing the factorial of 5 recursively calls factorial(4), which calls factorial(3), continuing until factorial(1) returns 1, then the results multiply back up through the call stack to give 120.”
Synonyms
- self-referential function
- recursive function
- divide-and-conquer
Antonyms / Opposites
- iteration
- iterative loop
Images
CC-licensed · free to useLoading images…
Video
Related Terms
- Algorithm
- Binary Tree
- Stack
- Dynamic Programming