19,936 views
41 votes
41 votes

Which of the following are true?

  1. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

  2. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

  3. Recursion in programming languages cannot be implemented with dynamic storage allocation

  4. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

  5. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

  1. II and V only
  2. I, III and IV only
  3. I, II and V only
  4. II, III and V only

7 Answers

Best answer
36 votes
36 votes
  1. False. Recursion cannot be implemented using static allocation.
  2. True. Yes, we do need multi level access link in case of nested functions. Each level to traverse ARB of same level of nesting.
  3. False. Recursion can only be implemented using dynamic memory allocation.
  4. False. Recursion is done using memory in stack (ARBs in stack), not in heap.
  5. True. Yes, they cannot, once a function returns its activation record is no longer valid, so we cannot return a function as a result.


So, option (A) is correct.

edited by
42 votes
42 votes

Answer is A.


1. is False, Recursion can not be implemented using static storage allocation.

Explanation:
in static storage allocation, a single value is reserved at compile time for each parameter and local variable of a function.
No place is provided to store any intermediate values calculated by repeated nested calls to the same function. Therefore, systems with only static storage allocation can not support recursion.

factorial (static int n)
{
if (n<=1)
return 1;

else
return (n*fact(n-1))
}

If you run this program for any value of n, say n=4. fact(4) will give output as 1.

2. is True.
Explanation: See my comment here.

3. False
We use run time stack that is one of the portion of Dynamic storage (Other portion is Heap, Both grows in opposite direction)

4. False (explanation same as above)

5. True
Explanation:  See this Code (Java script), Here function a() returns a function itself that is b().

function a() {

    alert('A!');

    function b(){
        alert('B!');
    }

    return b();
}

var s = a();

This wont be possible using stack, once activation record of a() pops out (remeber a() returns b()), now we need b(), bcoz a() just returned b(), And b() was defined in a() which no longer exists.

14 votes
14 votes
Answer is A.

I. Recursion can never be implemented with Static Storage Allocation.

II, Is TRUE.  

III. Recursion can be implemented with Dynamic Storage Allocation but not with Static Storage Allocation.

IV. Can be done with Stack based allocation scheme.

V. Is TRUE as with a stack based allocation once a function returns its activation record is no longer valid- so we cannot return a function as a result.
1 votes
1 votes

option- a

I.  Recursion cannot be implemented with Static Storage Allocation.   Static allocation means, compiler has to decide size for function calls.  In case of recursion, it is not possible for compiler to decide as depth of recursion depends on recursion parameter which may be an input from user also.

II. Is CORRECT.  Programming languages that support nested subroutines also have a field in the call frame that points to the stack frame of the latest activation of the procedure that most closely encapsulates the callee, i.e. the immediate scope of the callee. This is called an access link or static link (as it keeps track of static nesting during dynamic and recursive calls) and provides the routine (as well as any other routines it may invoke) access to the local data of its encapsulating routines at every nesting level. Some architectures, compilers, or optimization cases store one link for each enclosing level (not just the immediately enclosing), so that deeply nested routines that access shallow data do not have to traverse several links; this strategy is often called a “display”

III. Recursion CAN be implemented with any kind of  Dynamic Storage Allocation scheme.

IV. Nesting features are always implemented in a language using STACK and NOT Heap. (See above point II for details)

V. Is CORRECT.  In stack based allocation scheme, once a function has returned, it is removed from function call stack.  Therefore returning a function from a function doesn’t look possible.

Answer:

Related questions

39 votes
39 votes
3 answers
1
37 votes
37 votes
3 answers
3
Kathleen asked Sep 12, 2014
15,653 views
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only ifThe SLR(1) parser for G has S-R conflictsThe LR(1) parser for G has S-R conflictsThe...