GATE CSE 2008 | Question: 54

Question

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

• A. II and V only
• B. I, III and IV only
• C. I, II and V only
• D. II, III and V only

Comments

@Prashant_Dubey  

Func1() {
      Func1()      => This is nesting of function right ! but in option its given nesting is not there

}   

So we wont be having recusive function  thus won't be requiring dynamic memory allocation.

PS : Or nesting could mean :

Func1() {
      Func2()

}

and Recursion :

Func1() {
      Func1()  // Recusion but not Nesting of Function.

}   

In that case yes we would now require dynamic memory allocation

---

Recursion can't be implemented with static storage allocation otherwise value of variable in a (recursive) function will get overwritten.

---

nested functions means the function defined in another function or procedure but recursion is not that . recursion is the concept of calling the function itself

Answer 1

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.

Comments

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

---

About 4th point

Nesting of procedure / function and recursion require a dynamic heap allocation is TRUE

BUT THE POINT SAYS FUNCTION / PROCEDURE CANNOT BE IMPLEMENTED WITH A STACK BASED ALLOCATION WHICH IS FALSE

RECURSION IS SUPPORTED IN BOTH HEAP / STACK ALLOCATION

Answer 2

 

Answer: A

1. False — Recursion cannot be implemented using static storage allocation.

In static storage allocation, a fixed amount of memory is reserved at compile time for each parameter and local variable of a function. Since no additional storage is provided for repeated calls, intermediate values from nested recursive calls cannot be preserved. Hence, systems with only static storage allocation cannot support recursion.

factorial (static int n)
{
    if (n <= 1)
        return 1;
    else
        return (n * fact(n - 1));
}

If this program is executed for any value of \( n \), say \( n = 4 \), then \( \text{fact}(4) \) will always return \( 1 \).

2. True

Explanation: See the detailed discussion here.

3. False

Recursion is implemented using a runtime stack, which is part of the dynamic storage area. The memory layout during execution typically includes two dynamically growing regions — the stack and the heap, which grow in opposite directions.

The stack is used for function activation records and supports recursion by maintaining each call’s context separately.

4. False — Same reasoning as above.

5. True

Consider the following Python code, where the function \( a() \) returns another function \( b() \):

def a():
    print("A!")

    def b():
        print("B!")

    return b

s = a()   # a() returns the function b
s()       # now call b()

This behavior is not possible using only a stack. Once the activation record of \( a() \) is popped from the runtime stack, the nested function \( b() \), defined inside \( a() \), would no longer exist. However, since \( a() \) returns \( b() \), we must retain its reference even after \( a() \) completes — which requires dynamic (heap-based) storage for closures and function objects.

Comments

now we need b(), bcoz a() just returned b(), And b() was defined in a() which no longer exists.

Why do we even need b()? b() is a function while only b is a reference to a function. The function a() has already returned b(). So there should be no error. 

So, why can’t we use stack allocation scheme? 

---

@Deepak Poonia @Sachin Mittal 1 @GO Classes Arjun

Hi sir, can you please check the doubt of @MiNiPanda? Is it right? I am unable to understand the 5^th point.

---

@Sachi Saxena 11 sir , we can have stack based storage allocation scheme for activation records reffer the example here https://www.youtube.com/watch?v=mMK-TlvH5c4 NPTEL lecture . So the 5th point should be False

Example,

p(){
    ----
    return g();
}

When return g() runs , the stack appends the activation record(AR) of g() and not pops the AR of p(). After the g() returns then only p() returns and AR of it gets popped

Answer 3

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.

Comments

@ 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?

Answer 4

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 5

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/

Answer 6

We read option I - it's false.

So we hv to decide between only A and D and to do that we need to determine whether III is true or false.

III is false so option A is the ans.

Comments

I approached the same way ... :)