The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

Which of the following statements are CORRECT?

  1. Static allocation of all data areas by a compiler makes it impossible to implement recursion. 
  2. Automatic garbage collection is essential to implement recursion. 
  3. Dynamic allocation of activation records is essential to implement recursion. 
  4. Both heap and stack are essential to implement recursion. 
  1. $1$ and $2$ only
  2. $2$ and $3$ only
  3. $3$ and $4$ only
  4. $1$ and $3$ only
asked in Compiler Design by Veteran (106k points)
edited by | 2k views
None of the answer given below are clear.

Even the best answer is using answer elimination.

2 Answers

+23 votes
Best answer

It will be D.

option 2 is wrong because it is not necessary to have automatic garbage collection to implement recursion.

option 4 is wrong because it says that both are required to implement recursion, which is wrong. Either of them will suffice.

answered by Boss (19.7k points)
edited by
Can we implement recursion with just heap and not stack?
yes. Allocation and deallocation can be done at any time in Heap. It also supports recursion.
Actually it is not possible. Recursion needs a stack structure. It can be done using a heap, but then we have to simulate s stack using the heap.
Sir , what is the meaning of dynamic allocation of activation record , since dynamic allocation occurs in the heap while we have activation record in the stack .
Why d is incorrect? We need stack for storing functions local variables, and if each function uses dynamically allocated variables (suppose malloc() is used) then we also need heap area. So, aren't they both essential? Moreover, for option A, don't we need dynamic allocation scheme for data areas as we don't know beforehand how many function calls are going to be there?
@Arjun sir:
simulating a stack using heap means: we shouldn't consider this case?
in lisp activation record are allocated in Heap . So then 1 and 3 can be correct .
yes, stack structure is required for recursion bcoz, in a heap, allocation & de-allocation is done randomly.
Dynamic allocation means allocating the required portion of memory during run-time.

In the stack the memory for storing activation records is allocated at run-time according to actual function calling sequence.

Hence allocating stack space for Activation Records is also dynamic allocation, as it is done during run time.

@Arjun Sir

Heap is having structure as CBT ..but for Recursion we need LIFO structure ...which only stack can provide ..

Is this right sir ??

+8 votes

1) In Static allocation of memory , we cannot implement recursion. As in recursion we cannot determine at first how many time function will be called

2)Automatic garbage collection done in JAVA (JVM done this) and LISP. But recursion we can implement in C too.So, Automatic Garbage Collection is not essential for Recursion

3) True. Same reason as 1)

4)Stack implement recursion, but heap is not necessary for recursion

answered by Veteran (101k points)
@arjun sir if one of the option is given as 1,3,4 then we click on this option ?? in exam plz reply
@rajan statement 4 is false because either of them (heap or stack) is sufficient to implement recursion.
@akash.dinkar12 Option 1 says static allocation ie stack is imp , Option 2 says heap is also important ie dynamic allocation is also imp .So both of them are needed making Option 4 right. Am i right?

Related questions

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

42,599 questions
48,599 answers
63,723 users