Recursive Algorithms
- Recursive algorithms are a fundamental concept in computer science, allowing problems to be solved by breaking them down into smaller, more manageable subproblems.
- In this section, we will focus on constructing and tracing simple, non-branching recursive algorithms in a programming language.
Key Principles of Recursion
- Base Case:
- The condition that stops the recursion.
- Without a base case, the recursion would continue indefinitely, leading to a stack overflow error.
- Recursive Case:
- The part of the function where it calls itself with a modified argument, moving closer to the base case.
Recursion is often used when a problem can be divided into smaller subproblems of the same type.
Constructing a Simple Recursive Algorithm
- Let's start with a classic example: calculating the factorial of a number.
- Factorial is the product of all positive integers up to a given number $n$, denoted as $n!$.
Recursive Factorial Function
Consider the mathematical definition of factorial:
$$n! = n \times (n-1)!$$
With the base case:
$$1! = 1$$
ExampleHere's how we can implement this in Python:
def factorial(n):
# Base case
if n == 1 or n == 0:
return 1
# Recursive case
else:
return n * factorial(n - 1)
# Example usage
print(factorial(5)) # Output: 120Notice how the function calls itself with a smaller argument $(n - 1)$, moving closer to the base case.
Tracing a Recursive Algorithm
Tracing a recursive algorithm involves following the sequence of function calls and returns. Let's trace factorial(4):
- Call: factorial(4)
- Recursive Case: Returns 4 * factorial(3)
- Call: factorial(3)
- Recursive Case: Returns 3 * factorial(2)
- Call: factorial(2)
- Recursive Case: Returns 2 * factorial(1)
- Call: factorial(1)
- Base Case: Returns 1
