Data Structure Stack is used to implement recursive algorithm for computing factorial.
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.
- [Save N and return Address]
CALL PUSH (S, TOP, TEMP_REC)
- [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
- [Calculate N!]
FACTORIAL<--N * FACTORIAL
- [Restore previous N and return address]
TEMP_REC<--POP(S,TOP)
(i.e. PARAM<--N, ADDRESS<--RET_ADDR)
GO TO ADDRESS
