Question

Iterative implementation of a recursive algorithm executes faster than recursive implementation because no _____ needs to be maintained.

Select one:

a. recursion

b. iteration

c. recurrence

d. stack

e. array

Answer 1

Definitions:

Recursion: A function calling itself is called as Recursion

Example: consider a function fun as below

fun(n)

{

if(n<0)

return 0;

else

return fun(n-1)+1;

}

for, suppose user invokes fun(4) then

fun(4) calls fun(3)

fun(3) calls fun(2)

fun(2) calls fun(1)

fun(1) calls fun(0)

the result returned value will be 4

Iteration: A set of instructions executing repeatedly

Example: consider the following loop

c=0;

for(i=0;i<4;i++)

{

c=c+1;

}

here, for loop runs for i=0,1,2,3

and the result we get c=4

Answer: no stack needs be maintained for iteration.

Explanation: Observe the given example for Recursion above, there given function fun(n) calling fun(n-1) if n<0

Here, a stack is maintained to store different values of function fun with various parameters of n

For suppose, see the below case

if fun(n) is invoked by user and n>0 then add fun(n) to the top of the stack

if fun(n) calls fun(n-1) and n>0 then add fun(n) to the top of the stack

if fun(n-1) calls fun(n-2)and n>0 then add fun(n-1) to the top of the stack

this process of adding contents to stack occurs until function stops calling itself.

if a function stops calling itself then remove the element in the top of the stack.

if the stack is empty that means Recursion task is completed

Here, stack is used to trace the sequence of function calling in Recursion.

Iteration do not contain calling functions itself so iteration do not need stack

so maintaining stack is a time taking process to the Recursion. So Iteration is faster than Recursion

If you have any doubts feel free to ask me in comments

Have a nice day.!!