In: Computer Science
Would the following function work correctly if statically allocated activation records are used for implementation? Explain why it would work or not.
fun fact x = if x <= 0 then 1 else x * fact(x - 1);
Answer:-
No, the following function will not work if statically allocated activation records are used for implementation because the problem is that each recursive call needs to remember the value of its argument and return address, i.e., we need two storage locations for each active call to fact(). for example, while executing fact(4), we need to call fact(3), fact(2), fact(1) and finally get to call fact(0) there are five nested active calls, so we’ll need 5*2 = 10 storage locations. In fact, the amount of storage needed varies with the depth of the recursion that is how many recursions we are doing. That's why we can’t use statically allocated activation record to hold all the values we need to save during this execution
.
so, we can’t statically allocate a single block of storage for this function as recursive calls means that we’ll have many active calls to that procedure at points during the execution.