4
$\begingroup$

I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more efficiently than that in terms of recursion.

EDIT:

Let us go further, do you think iteration would be better than recursion to complexity?

|cite|improve this question
$\endgroup$
  • 7
    $\begingroup$ Primitive recursion was invented before programming. $\endgroup$ – Dave Clarke Jun 17 '11 at 20:00
  • $\begingroup$ Hmm, so you mean they were not aware of iteration when primitive recursion was invented? $\endgroup$ – day Jun 17 '11 at 20:18
  • 2
    $\begingroup$ Huh? I would like to challenge the assumption that recursion is less efficient than iteration. Some programming languages implement recursive calls inefficiently, but that doesn't imply anything about the general phenomena. $\endgroup$ – Ohad Kammar Jun 17 '11 at 20:22
  • $\begingroup$ See Type Fixpoints: Iteration vs. Recursion, page 2. $\endgroup$ – user76284 Nov 15 '16 at 0:35
30
$\begingroup$

Iterators of any kind are just a form of recursion, i.e., a thing "using itself". For example, the basic equation governing the while loop is

(while b do C) = (if b then (C; while b do C))

You may think I am doing something exotic, but as soon as you try to explain what recursion and iteration mean, you will end up writing such equations. For example, people tend to explain the while loop by saying things like "and so on" (imprecise) or "do C while b" (not explaining anything), or "keep doing" (circular explanation). The above equation tells you everything there is to know about the while loop. Similar arguments can be made about other forms of iteration.

The above equation is recursive, as the defined term appears on both sides. The general form is $$x = \phi(x),$$ which of course is just a general recursive definition of $x$. In this sense iteration is just a special form of recursion. So as far as theory is concerned, there is pratically no difference between recursion and iteration, except that the latter is a special case of the former. And both concepts are special cases of fixed point equations, a very important and general mathematical concept. This answers why "they chose recursor instead of iterator".

Your claim that iteration is more efficient than recursion is bogus. Modern programming languages are quite efficient at both of these tasks. In any case, it is not the job of humans to think about low-level details of execution of programs (maybe that was the case in the 1960's when the total amount of CPU power and memory on the planet was comparable to what kids carry in their pockets these days). We have better things to do as programmers, such as how to write programs most efficiently and how to make sure they are actually correct.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ +1 for a good explanation, but I do not agree with the claim that "it is not the job of humans to think about low-level details of execution of programs". Performance engineering courses are increasingly relevant these days. In 1960s things were simple; nowadays we have increasingly complicated platforms with memory hierarchies and multiple cores. $\endgroup$ – Jukka Suomela Jun 18 '11 at 12:04
  • 11
    $\begingroup$ Let me be more precise: it is not the job of most programmers to think about low-level details. It is a mistake to emphasize efficiency before structure and correctness. $\endgroup$ – Andrej Bauer Jun 18 '11 at 12:52
  • 4
    $\begingroup$ While it's usually a mistake to prematurely optimize, there are certainly cases where efficiency is a component of correctness. Multimedia is a good example here -- a video decoder that doesn't perform up to the required frame rate is incorrect in a fundamental way. $\endgroup$ – Sam Tobin-Hochstadt Jun 18 '11 at 22:30
  • 4
    $\begingroup$ Most programmers do not write video decoders. $\endgroup$ – Andrej Bauer Jun 19 '11 at 6:39
  • 4
    $\begingroup$ There is, of course, no kind of program that most programmers write. But it's a mistake to be too dismissive of performance, in many domains. $\endgroup$ – Sam Tobin-Hochstadt Jun 19 '11 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.