recategorized by
6,340 views
24 votes
24 votes

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

  1. Recursive programs are more powerful than iterative programs.
  2. For every iterative program there is an equivalent recursive program.
  3. Recursive programs require dynamic memory management.
  4. Recursive programs do not terminate sometimes.
  5. Iterative programs and recursive programs are equally expressive.
recategorized by

2 Answers

21 votes
21 votes

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.

edited by
15 votes
15 votes

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

 

 

Answer:

Related questions