- 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:
fibonacci of 5: