Recursion
A programming technique where a function calls itself to solve smaller instances of the same problem.
Recursion
Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. Each recursive call addresses a smaller instance of the same problem, moving toward a base case that can be solved without further recursion.
A recursive algorithm typically consists of two essential parts:
- Base case(s): Simple instances of the problem that can be solved directly without further recursion
- Recursive case(s): More complex instances that are solved by breaking them down and involving recursive calls
Recursion naturally maps to problems that can be broken down into smaller, similar subproblems, particularly those with a hierarchical or nested structure. It often leads to elegant and concise solutions to complex problems.
While recursion can be powerful and intuitive, it has some limitations:
- Each recursive call consumes stack space, which can lead to stack overflow errors for deep recursion
- Recursive solutions may have more overhead than iterative alternatives due to function call machinery
- Simple recursive implementations of some algorithms can lead to redundant calculations
Techniques like tail recursion, memoization, and dynamic programming can help address these limitations in many cases.
Examples
- Factorial calculation: factorial(n) = n * factorial(n-1), with factorial(0) = 1
- Fibonacci sequence: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), with fibonacci(0) = 0 and fibonacci(1) = 1
- Binary tree traversal: Process the current node, then recursively process left and right subtrees
- Merge sort: Recursively sort the two halves of an array, then merge them
Code Example
// Recursive factorial function
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Recursive fibonacci function
function fibonacci(n) {
// Base cases
if (n <= 0) return 0;
if (n === 1) return 1;
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}Related Terms
Divide and Conquer
An algorithmic paradigm that solves problems by breaking them into smaller subproblems, solving each independently, and combining the results.
Dynamic Programming
A method for solving complex problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant computations.
Algorithm
A step-by-step procedure for solving a problem or accomplishing a task.
Further Learning
Want to see these concepts in action?