The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.6k views

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
asked in Programming by Veteran (68.8k points) | 1.6k views

5 Answers

+13 votes
Best answer

I. False. Recursion cannot be implemented using static allocation.
II. True. Yes, we do need multi level access link in case of nested functions. Each level to traverse ARB of same level of nesting.
III. False. Recursion can only be implemented using dynamic memory allocation.
IV. False. Recursion is done using memory in stack (ARBs in stack), not in heap.
V. 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.

answered by Boss (9.3k points)
selected by
what about 5th one?
Sorry I missed IV point. Now check :)
By ARB u mean to say "activation record block"?
yes
and in (v) if we can't use stack based storage allocation scheme then which scheme it will use?
No idea!
ok thanks :)

@monanshi

" Multi-level access link (or display) arrangement is needed to arrange activation records "

Why need to arrange activation records?

Can functions be returned as a result of a function call in any programming language?

In c we return pointer to function but not  function itself.So , cant we use pointers to get this done?

Also,if value,string etc. can be returned then why cannot a function be returned?

What is the difference between first option in this question and first option in this https://gateoverflow.in/2052/gate2014-3-18

+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.
answered by Veteran (19.6k points)
stcak can be implemented using static storage allocation but that stack may overflow too early .
how V can be true .For nesting or recursion we need stack based ​storage.
Recursion cannot be implemented with Static Storage Allocation. Recursion with Static allocation means, compiler has to decide size of all functions to be called; It is not possible for compiler to decide the depth of recursion beforehand.
where is the returned value stored??
in which ?
i mean when a function has to return value where is this returned value stored so that it can be returned to the calling function successfully??
@ Saurabh, thanx a lot :)

sushmita @ saurabh rai 

Can you Pease help in understanding how 5th is true? Returning a function is something different than returning a value?We can return the address of the function as a return value?

If A calls B,the does A's register for return value hold the value return by B?
+10 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.

answered by Veteran (13.3k points)
0 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.

answered by Veteran (16.6k points)
0 votes

Explanation: 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”  [Source:  https://en.wikipedia.org/wiki/Call_stack ]

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.

source:_https://www.geeksforgeeks.org/gate-gate-cs-2008-question-54/

answered ago by Boss (7.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,503 questions
39,217 answers
109,114 comments
36,599 users