Even the best answer is using answer elimination.

31 votes

Which of the following statements are CORRECT?

- Static allocation of all data areas by a compiler makes it impossible to implement recursion.
- Automatic garbage collection is essential to implement recursion.
- Dynamic allocation of activation records is essential to implement recursion.
- Both heap and stack are essential to implement recursion.

- $1$ and $2$ only
- $2$ and $3$ only
- $3$ and $4$ only
- $1$ and $3$ only

0

Recursion can not be implemented without stack. Heap is not needed in recursion if there is no use of dynamic memory allocation like pointers.

4

**Answer:** **(D)**

**Explanation:** **1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.**

True, dynamic allocate of memory is required for function call stack as number of calls is not known advance for recursive functions.

**2) Automatic garbage collection is essential to implement recursion.**

False, Automatic garbage collection is not essential.

**3) Dynamic allocation of activation records is essential to implement recursion.**

True, as number of calls or number of activation records is not known advance for recursive functions.

**4) Both heap and stack are essential to implement recursion.**

Heap is not needed for function calls. It is generally used for dynamic memory allocation by user (or programmer).

Source: https://www.geeksforgeeks.org/gate-gate-cs-2014-set-3-question-28/

33 votes

Best answer

50

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.

http://stackoverflow.com/questions/2807131/recursion-using-only-heap-area

http://stackoverflow.com/questions/2807131/recursion-using-only-heap-area

1

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 .

1

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?

1

yes, stack structure is required for recursion bcoz, in a heap, allocation & de-allocation is done randomly.

2

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.

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.

0

@Arjun Sir

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

Is this right sir ??

0

@arjun sir, with this **" 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" **statement, given by you,

can we say that option 4 would also be correct if it we are asked about only "recursion need heap and stack both in case if we are trying to implement recursion using heap "?

16 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

0

1

@rajan statement 4 is false because either of them (heap or stack) is sufficient to implement recursion.

0

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

0

Statement 1st is easy and we got it directly from nptel by sir **YN srikant Lectures on run time environment.**

*statement 2nd is also well understood as we know c not allowed automatic GC and we can implement recursion there.*

*statement 4th is also fine there is quite difficulties to implementation recursion in heap because we know heap allow random allocation and de-allocation and moreover there is a simulation required for a well formed data structure.*

*Only Statement 3rd i am not getting here can anybody explain this? *

Acc to my point of view activation record is created whenever there will be a entry of a procedure thats why there is a need of recursion.

Correct me...

1 vote

This question can be solved by option elimination.

See the 4 th statement, it says both stack and heap are essential to implement recursion. But we know that only stack is enough to implement recursion. Hence 4 th statement is false.

Similarly statement 2 says automatic garbage collection is essential for recursion which is again false as there is no relationship of automatic garbage collection and recursion.

So statement 4 and 2 are false.

Hence we are left with **only** **D ****as the correct answer.**