Recursion

Question

Identify the false statement a. When a module calls a subroutine recursively ,in each call , all of the information is popped in the same order when sub routines are terminated one after another and finally the control is returned to the calling module b. A recursion algorithm has two elements: each call either solves only part of the problem or it reduces the size of the problem

Answer 1

I think the option A is false . and second one is right .
The first statement is false because all the calls are pushed in the same order while the popping is done in  the reverse order . so the option  a will be wrong . and statement b can be right about the recursion because yes the recursive algorithms either decrease the size or solve it completely.

Comments

& what about stack overflow ?? Neither it will reduce size nor solve it completely.

"Either it will solve completely or it will reduce size" is property of Devide & Conquer.

---

@Digvijay What is meaning of size of the problem here ? Is it size of program or space taken by recursive procedure?

---

i think as stated algorithm not a program . stack overflow will not be the case . in such a situation. @digvijay

Answer 2

When a module calls a subroutine recursively ,in each call , all of the information is popped in the same order when sub routines are terminated one after another and finally the control is returned to the calling module  This is false ..

But the second statement A recursion algorithm has two elements: each call either solves only part of the problem or it reduces the size of the problem is not correct.

Using recursion increases the size is program.It takes  extra stack space.

Comments

Why it takes O(log n) extra space and not O(n)?