Question

(O polnto int fint n) int t, s if (n < 2) teturn 1 fa-1); tfa-2); return s+ +SS CaatloatCala*5 aat $5+s 4a4 $5.+ 554 a taata b. Consider the above code soippet. Assume that the initial call is f(5), deaw the activation tree. (8 points) Briefly explain the tem "Garbage collection" as it relates to compiler construction c. (3 points)

Answer 1

b. The process for drawing Activation Tree and Activation Tree when the initial call is f(5) is as follows :-

Activaton Tree -

Activation Tree retrrn 8 fls) St 5 4-3 fl4) redurn neduon f(3) S 3 t2 Se2 421 relurn fle) 2 f(1) S2 tei rehurn S21 1 relurn fly (G Yesturn (- tes f(1) 2 Yecu rm return retunn returm 1 eturn neturm 1

Process -

I will write the function will are called and assign a number to them for simplicity.

First the function f(n) where n = 5 will be called. - f(5) = Num1

-> Next function f(n-1) where n = 5 will be called. - f(4) = Num2

-> Next function f(n-1) where n = 4 will be called. - f(3) = Num3

-> Next function f(n-1) where n = 3 will be called. - f(2) = Num4

-> Next function f(n-1) where n = 2 will be called. - f(1) = Num5

The function Num5 i.e. f(1) return the value 1 as n<2, which will be stored in s of Num4.

-> Next function f(n-2) where n = 2 will be called. - f(0) = Num6

The function Num6 i.e. f(0) return the value 1 as n<2, which will be stored in t of Num4.

The function Num4 i.e. f(2) return the value s+t = 2 , which will be stored in s of Num3.

-> Next function f(n-2) where n = 3 will be called. - f(1) = Num7

The function Num7 i.e. f(1) return the value 1 as n<2, which will be stored in t of Num3.

The function Num3 i.e. f(3) return the value s+t = 3 , which will be stored in s of Num2.

-> Next function f(n-2) where n = 4 will be called. - f(2) = Num8

-> Next function f(n-1) where n = 2 will be called. - f(1) = Num9

The function Num9 i.e. f(1) return the value 1 as n<2, which will be stored in s of Num8.

-> Next function f(n-2) where n = 2 will be called. - f(0) = Num10

The function Num10 i.e. f(0) return the value 1 as n<2, which will be stored in t of Num8.

The function Num8 i.e. f(2) return the value s+t = 2 , which will be stored in t of Num2.

The function Num2 i.e. f(4) return the value s+t = 5 , which will be stored in s of Num1.

-> Next function f(n-2) where n = 5 will be called. - f(3) = Num11

-> Next function f(n-1) where n = 3 will be called. - f(2) = Num12

-> Next function f(n-1) where n = 2 will be called. - f(1) = Num13

The function Num13 i.e. f(1) return the value 1 as n<2, which will be stored in s of Num12.

-> Next function f(n-2) where n = 2 will be called. - f(0) = Num14

The function Num14 i.e. f(0) return the value 1 as n<2, which will be stored in t of Num12.

The function Num12 i.e. f(2) return the value s+t = 2 , which will be stored in s of Num11.

-> Next function f(n-2) where n = 3 will be called. - f(1) = Num15

The function Num15 i.e. f(1) return the value 1 as n<2, which will be stored in t of Num11.

The function Num11 i.e. f(3) return the value s+t = 3 , which will be stored in t of Num1.

Finally, the function Num1 i.e. f(5) return the value s+t = 8.

The total function calls made to function f(int ) are 15.

c. GARBAGE COLLECTOR :-

Whenever the user creates objects dynamically with the help of new keyword and malloc() method etc., the objects are allocated memory in the heap. In some programming languages like C and C++ etc. the user, both creates and destroys the objects manually. But in some programming languages like java etc. the user need not to destroy the objects as Garbage Collector which is an automatic memory management feature, destroys the objects which are unreachable.
Garbage Collection removes the heap memory of the unreachable objects. It automatically detects all the unreachable objects in our program and free the respective heap memory which is allocated to the objects.
The methods generally used for Garbage collection are Tracing, Reference Counting and Escape Analysis. There are many Garbage Collection algorithms such as Mark and Sweep algorithm, Cheney's algorithm, Baker's algorithm, Lieberman's algorithm etc.

Example of Garbage Collection:-
String Ch = new String('Hello');
//here, the new String object can be reached through the reference of Ch.
Ch = NULL;
//Now, the String object is not reachable.

Therefore, the String Object Hello is available for Garbage Collection. In Java, it happens automatically while in C/C++ it is done manually by User.