Page 172 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

The new values of num, num-1, fact (num-1) and (num * fact (num-1)) are depicted in table 9.1 (f) as the
execution proceeds.

Table 9.1: Illustrations of Stack while Determining fact (4)

4 … … … 1000
num num-1 fact(num-1) num*fact(num-1) Program Counter
fact(4) in main()
(a)

4 3 … … 2000
4 … … … 1000
num num-1 fact(num-1) num*fact(num-1) Program Counter
fact(4)
(b)

3 2 … … 2000
4 3 … … 2000
4 … … … 1000
num num-1 fact(num-1) num*fact(num-1) Program Counter
fact(3)
(c)

2 1 … … 2000
3 2 … … 2000
4 3 … … 2000
4 … … … 1000
num num-1 fact(num-1) num*fact(num-1) Program Counter
fact(2)
(d)

1 0 … … 2000
2 1 … … 2000
3 2 … … 2000
4 3 … … 2000
4 … … … 1000
num num-1 fact(num-1) num*fact(num-1) Program Counter
(e)

num num-1 fact(num-1) num*fact(num-1)
1 0 1 1
2 1 1 2
3 2 2 6
4 3 6 24
(f)
Finally, the control passes onto the main () program. The value 24 is copied into (num * fact (num-1)). A
function can be invoked many times to solve a problem which is termed as depth of recursion. ‘num’ is
called the depth of recursion to calculate fact (num).

LOVELY PROFESSIONAL UNIVERSITY 165