Definition
Recursion in programming is a technique where a function calls itself directly or indirectly to solve a problem. Each recursive call typically solves a smaller instance of the original problem, and the process continues until a base case is reached, which stops further recursion.
Worked Example
Problem: Compute the factorial of a non-negative integer $n$, denoted as $n!$.
Recursive Definition:
$$ n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases} $$
Recursive Function (in pseudocode):
``
function factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Example Calculation:
Calculate $4!$:
\[\begin{align*} factorial(4) &= 4 \times factorial(3) \\ &= 4 \times (3 \times factorial(2)) \\ &= 4 \times (3 \times (2 \times factorial(1))) \\ &= 4 \times (3 \times (2 \times (1 \times factorial(0)))) \\ &= 4 \times 3 \times 2 \times 1 \times 1 \\ &= 24 \end{align*}\]
Key Takeaways
- Recursion is when a function solves a problem by calling itself with smaller inputs.
- Every recursive function must have a base case to prevent infinite calls.
- Recursion is useful for problems that can be broken down into similar subproblems, such as factorial, Fibonacci, and tree traversals.