Introduction
Recursive functions are a powerful concept in programming where a function calls itself to solve a problem. This technique is particularly useful for problems that can be broken down into smaller, similar sub-problems. In this section, we will explore how to define and use recursive functions in ALGOL.
Key Concepts
- Base Case: The condition under which the recursion stops.
- Recursive Case: The part of the function where the function calls itself.
- Stack Overflow: A potential issue if the recursion does not terminate properly.
Defining Recursive Functions in ALGOL
Example: Factorial Function
The factorial of a non-negative integer \( n \) is the product of all positive integers less than or equal to \( n \). It is denoted as \( n! \).
Mathematical Definition:
- \( 0! = 1 \) (Base Case)
- \( n! = n \times (n-1)! \) for \( n > 0 \) (Recursive Case)
ALGOL Code
begin
integer procedure factorial(n);
value n;
integer n;
begin
if n = 0 then
factorial := 1
else
factorial := n * factorial(n - 1)
end;
integer n;
n := 5;
print("Factorial of ", n, " is ", factorial(n));
end;Explanation
- Base Case:
if n = 0 then factorial := 1- When \( n \) is 0, the function returns 1.
- Recursive Case:
else factorial := n * factorial(n - 1)- For \( n > 0 \), the function calls itself with \( n-1 \) and multiplies the result by \( n \).
Practical Exercises
Exercise 1: Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.
Mathematical Definition:
- \( F(0) = 0 \)
- \( F(1) = 1 \)
- \( F(n) = F(n-1) + F(n-2) \) for \( n > 1 \)
Task: Write a recursive function in ALGOL to compute the \( n \)-th Fibonacci number.
Solution
begin
integer procedure fibonacci(n);
value n;
integer n;
begin
if n = 0 then
fibonacci := 0
else if n = 1 then
fibonacci := 1
else
fibonacci := fibonacci(n - 1) + fibonacci(n - 2)
end;
integer n;
n := 10;
print("Fibonacci number ", n, " is ", fibonacci(n));
end;Explanation
- Base Cases:
if n = 0 then fibonacci := 0andelse if n = 1 then fibonacci := 1- When \( n \) is 0 or 1, the function returns 0 or 1, respectively.
- Recursive Case:
else fibonacci := fibonacci(n - 1) + fibonacci(n - 2)- For \( n > 1 \), the function calls itself with \( n-1 \) and \( n-2 \) and sums the results.
Common Mistakes and Tips
- Infinite Recursion: Ensure that your recursive function has a well-defined base case to prevent infinite recursion and potential stack overflow.
- Efficiency: Recursive functions can be inefficient for large inputs due to repeated calculations. Consider using memoization or iterative solutions for optimization.
Conclusion
Recursive functions are a fundamental concept in programming that allow for elegant solutions to complex problems. By understanding the base and recursive cases, you can effectively implement recursion in ALGOL. Practice with different problems to become proficient in recognizing when and how to use recursion.
Next, we will explore Procedures in ALGOL, which will further enhance your ability to structure and modularize your code.