Dark Mode

5,299 views

22 votes

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

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

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.

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

1

14 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

0

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.

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.

5