TIFR CSE 2011 | Part B | Question: 38

Question

Consider the class of recursive and iterative programs. Which of the following is false?

• A. Recursive programs are more powerful than iterative programs.
• B. For every iterative program there is an equivalent recursive program.
• C. Recursive programs require dynamic memory management.
• D. Recursive programs do not terminate sometimes.
• E. Iterative programs and recursive programs are equally expressive.

Comments

http://www.cs.ucc.ie/~gprovan/CS4407/L3-Iterative-Programs.pdf

---

@VIKAS TIWARI

i didn't get any information related to this question from the link you shared !

Answer 1

Answer is option E.

Computable function: those which can be incorporated in a program using for/while loops.

Total Function: Defined for all possible inputs

Well Defined: if its definition assigns it a unique value.

It was a belief in early $1900$s that every Computable function was also Primitively Recursive. But the discovery of Ackermann function provided a counter to it.

The class of primitive recursive functions is a small subclass of the class of recursive functions. This means that there are some functions which are Well-Defined Total Functions and are Computable BUT Not primitively recursive; eg. Ackermann function.

This makes all options from option A to option D as True.

But option E as $\text{FALSE}$. As iterative programs are equivalent to only Primitively Recursive class.

Comments

arjun sir nested recursion is also a non primitive recursion

---

I don't think this answer is correct.

---

@Arjun sir from the above discussion can we say that recursive program is more powerful than iterative programs. Can you provide an example?

 

Answer 2

Answer is option $A$

$\text{A. Recursive programs are more powerful than iterative programs}$. 

This is $\text{false }$as there exist an iterative program for every recursive program.

Primitive recursive functions correspond to programs using bounded iteration, that is, you have to specify the number of iterations that a loop is executed in advance. Bounded iteration cannot simulate recursion in general, since the Ackermann function isn't primitive recursive. But unbounded iteration can simulate any partially computable function.

$\text{B. For every iterative program there is an equivalent recursive program.}$ True

$\text{C. Recursive programs require dynamic memory management.}$

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

$\text{D. Recursive programs do not terminate sometimes.}$ True

$\text{E. Iterative programs and recursive programs are equally expressive.}$

True.  Here is an "iterative" algorithm for the Ackermann function

 

 

Comments

I think option A is true. Consider tower of hanoi problem we don't have iterative program yet and hence we always use recursive approach so I think option E is false

---

This answer is correct, in my humble opinion.

The Church-Turing thesis (yet to be proved, but also yet to be unproved) tells you that everything that's "computable" can be computed by a Turing Machine. Turing Machine is an iterative model.

Any recursive program can be converted into an iterative version and vice versa. They have equal expressive powers.

 

Also, in my humble opinion again, the "if they're allowed to use a stack" is not a valid counter-point. Stack isn't the characteristic of recursion — it is the other way around. Recursion needs stack. Always. Doesn't mean that if you use a stack you're performing some recursive action.

Every local variable uses stack. If you just declare "int i" inside a function, it's saved in the stack. So every program that uses any variable is recursive?

 

No example exists that shows a recursive program that can't be implemented via iteration.

---

@khardnaman

You're one Google search away from editing that comment.