Recursion
A programming technique where a function calls itself to solve a problem by breaking it into smaller subproblems.
Definition
Recursion is a programming technique where a function solves a problem by calling itself with a simpler or smaller version of the same problem, until reaching a base case that can be solved directly. Recursion elegantly solves problems with self-similar structure, such as tree traversal, factorial calculation, Fibonacci sequence, and divide-and-conquer algorithms. Each recursive call creates a new stack frame; deep recursion can cause stack overflow errors. Many recursive solutions can be replaced with iterative solutions for efficiency.
Example
“A recursive factorial function: factorial(n) returns 1 if n equals 0, otherwise returns n times factorial(n-1). Calling factorial(5) unfolds to 5 times 4 times 3 times 2 times 1 equals 120.”
Synonyms
- self-referential function
- recursive call
- divide and conquer
Antonyms / Opposites
- iteration
- loop
- iterative solution
Images
CC-licensed · free to useVideo
Related Terms
- algorithm
- stack-overflow
- divide-and-conquer
- tree