Deprecated: Implicit conversion from float-string "1532412027.543" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1532412027.543" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1532412027.543" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1532412027.543" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1532412027.543" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539869940.117" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539869940.117" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539869940.117" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539869940.117" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539869940.117" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1535650640.178" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1535650640.178" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1535650640.178" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1535650640.178" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1535650640.178" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539842989.415" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539842989.415" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539842989.415" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539842989.415" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539842989.415" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1570374692.085" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1570374692.085" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1570374692.085" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1570374692.085" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1570374692.085" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539842833.361" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539842833.361" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539842833.361" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539842833.361" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539842833.361" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539861815.666" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539861815.666" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539861815.666" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539861815.666" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539861815.666" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539862356.444" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539862356.444" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539862356.444" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539862356.444" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539862356.444" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539863618.780" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539863618.780" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539863618.780" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539863618.780" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539863618.780" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539863871.331" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539863871.331" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539863871.331" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539863871.331" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539863871.331" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1539874397.617" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1539874397.617" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1539874397.617" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1539874397.617" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1539874397.617" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1577643581.285" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1577643581.285" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1577643581.285" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1577643581.285" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1577643581.285" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594

Deprecated: Implicit conversion from float-string "1577643777.463" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1577643777.463" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1577643777.463" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1577643777.463" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1577643777.463" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 594
TIFR CSE 2011 | Part B | Question: 38 / GATE Overflow for GATE CSE
recategorized by
6,437 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

1.7k
views
2 answers
9 votes
makhdoom ghaya asked Oct 22, 2015
1,726 views
Various parameter passing mechanisms have been in used in different programming languages. Which of the following statements is true?Call by value result is used in langu...
507
views
0 answers
3 votes
makhdoom ghaya asked Oct 20, 2015
507 views
Consider the programx:=0; y:=0; (r1:=x; r2:=x; y:= if r1 = r2 then 1 ∥ r3:= y; x:= r3)Note that ∥ denotes the parallel operator. In which of the following cases can t...
1.2k
views
2 answers
5 votes
makhdoom ghaya asked Oct 26, 2015
1,220 views
Consider the class of object oriented languages. Which of the following is true?Pascal is an object oriented language.Object oriented languages require heap management.Ob...
4.0k
views
3 answers
17 votes
makhdoom ghaya asked Oct 25, 2015
4,044 views
The first $n$ cells of an array $L$ contain positive integers sorted in decreasing order, and the remaining $m - n$ cells all contain 0. Then, given an integer $x$, in ho...
Total PHP MySQL Other RAM
Time (ms) % Time (ms) % File count Time (ms) % Query count Time (ms) % Amount %
Setup 4.6 3% 2.3 1% 72 2.4 1% 2 0.0 0% 569k 39%
Control 24.1 17% 1.7 1% 5 22.7 16% 12 0.0 0% 393k 27%
View 3.1 2% 3.1 2% 12 0.0 0% 0 0.0 0% 110k 7%
Theme 97.8 71% 4.7 3% 15 93.2 68% 3 0.0 0% 363k 25%
Stats 6.9 5% 0.1 0% 0 6.9 5% 1 0.0 0% 0k 0%
Total 136.6 100% 11.9 8% 104 125.1 91% 18 0.0 0% 1438k 100%