Recursive algorithm to compute factorial of a given number
Stack is used to implement this algorithm
Algorithm: FACTORIAL
- Given integer N, this algorithm computes factorial of N.
- Stack S is used to store an activation record associated with each recursive call.
- Each activation record contains the current value of N and the current return address RET_ADDE.
- TEMP_REC is also a record which contains two variables PARAM & ADDRESS.
- TOP is a pointer to the top element of stack S.
- Initially return address is set to the main calling address. PARAM is set to initial value N.
1. [Save N and return Address]
CALL PUSH (S, TOP, TEMP_REC)
2. [Is the base criterion found?]
If N=0
Then FACTORIAL<-- 1
GO TO Step 4
Else PARAM <-- N-1
ADDRESS <-- Step 3
GO TO Step 1
3. [Calculate N!]
FACTORIAL <-- N * FACTORIAL
4. [Restore previous N and return address]
TEMP_REC <-- POP(S,TOP)
(i.e. PARAM <-- N, ADDRESS <-- RET_ADDR)
GO TO ADDRESS
