Data Structure (2130702)

BE | Semester-3   Summer-2019 | 06/04/2019

Q2) (b)

Write recursive algorithm to compute factorial of a given number. Which data structure can be used to implement this algorithm?

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