- 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 i, n: int; main do n = 5; print("factorial of 5:"); print(factorial(n)); print(); print("fibonacci of 5:"); count i up 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:
fibonacci of 5: