Unit Eight - Recursive Algorithms

Question 1

Factorials

Answer 1

E.g. 5! = 5x4x3x2x1
The factorial function is a good example of a function that is defined in terms of itself. n!= n x (n-1)!

Question 2

A recursive subroutine example

Answer 2

SUB calc(n)
If n = 0 then
factorial=1
else
facrorial= n*calc(n-1)
print (factorial)
EndSUB

Question 3

How does it work?

Answer 3

Each time the subroutine is called, the return address, parameter and local variables are pushed onto the stack. Statement 6 is not reached until the routine is called with n=0, when 0!=1 is output. Then statement seven is reached so the next return address (6) is popped.

Question 4

Essential Characteristics of a recursive algorithm

Answer 4

There must be a stopping condition or base case so that when its met it will not call itself so it can start unwinding.
For all vales other than the base case, the routine must call itself
You must be able to reach the base case within a finite number of calls

Question 5

The use of the call stack

Answer 5

Every time the subroutine is called, the return address (the line after CALL statement) is put on the call stack. Even with a stopping conditions, the recursive routine can only be called for a limited number of times or the stack will overflow the maximum memory capacity.