Recursion
Posted: Thu Dec 30, 2021 4:50 pm
SharpBASIC supports recursion for subroutines and functions. When using recursion, always keep in mind the following three basic rules:
A base case is typically a problem that is small enough to solve directly. In the factorial algorithm the base case is n=1. We must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the factorial n decreases.
Example of recursive factorial and fibonacci:
Output:
factorial of 5:
120
fibonacci of 5:
0
1
1
2
3
- A recursive algorithm must call itself, recursively.
- A recursive algorithm must have a base case.
- A recursive algorithm must change its state and move toward the base case.
A base case is typically a problem that is small enough to solve directly. In the factorial algorithm the base case is n=1. We must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the factorial n decreases.
Example of recursive factorial and fibonacci:
Code: Select all
decl func factorial(n: int): int;
decl func fibonacci(n: int): int;
dim n: int;
dim i: iter;
main do
n = 5;
print("factorial of 5:");
print(factorial(n));
print();
print("fibonacci of 5:");
for i = 0 to n - 1 :++ do
print(fibonacci(i));
end
print();
end
func factorial(n: int): int
do
if n == 0 do
return 1;
end
factorial = n * factorial(n - 1);
end
func fibonacci(n: int): int
do
when n is 0, 1 do
return n;
end
fibonacci = (fibonacci(n - 1) + fibonacci(n - 2));
end
factorial of 5:
120
fibonacci of 5:
0
1
1
2
3