<p>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</p>

<blockquote>
  <p><code>(while b do C)</code>  =  <code>(if b then (C; while b do C))</code></p>
</blockquote>

<p>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 <code>while</code> loop by saying things like "and so on" (imprecise) or "do <code>C</code> while <code>b</code>" (not explaining anything), or "keep doing" (circular explanation). The above equation tells you everything there is to know about the <code>while</code> loop. Similar arguments can be made about other forms of iteration.</p>

<p>The above equation is <em>recursive</em>, 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 <em>iteration is just a special form of recursion</em>. 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".</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-18T12:04:19.500Z
+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](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2009/) are increasingly relevant these days. In 1960s things were simple; nowadays we have increasingly complicated platforms with memory hierarchies and multiple cores.
Jukka Suomela
CC BY-SA 3.0
2011-06-18T12:52:00.250Z
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.
Andrej Bauer
CC BY-SA 3.0
2011-06-18T22:30:22.720Z
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.
Sam Tobin-Hochstadt
CC BY-SA 3.0
2011-06-19T06:39:46.570Z
Most programmers do not write video decoders.
Andrej Bauer
CC BY-SA 3.0
2011-06-19T12:35:44.910Z
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.
Sam Tobin-Hochstadt
CC BY-SA 3.0
2011-07-01T21:31:42.680Z
I am not being dismissive. I am just stating that when programming is taught to beginners, performance should not come first. This was not so 40 years ago.
Andrej Bauer
CC BY-SA 3.0
2013-07-09T17:02:13.090Z
@AndrejBauer: Amen. Getting this stuff to work right at all is hard enough to begin with.
Mr. JavaScript
CC BY-SA 3.0
2011-06-18T06:18:05.653Z
2011-06-18T06:26:53.637Z
2011-06-18T06:26:53.637Z
Andrej Bauer
<p>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.</p>

<p><em>EDIT:</em></p>

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

CC BY-SA 3.0
2011-06-17T20:00:53.487Z
Primitive recursion was invented before programming.
Dave Clarke
CC BY-SA 3.0
2011-06-17T20:18:03.797Z
Hmm, so you mean they were not aware of iteration when primitive recursion was invented?
day
CC BY-SA 3.0
2011-06-17T20:22:40.597Z
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.
Ohad Kammar
CC BY-SA 3.0
2016-11-15T00:35:08.523Z
See [Type Fixpoints: Iteration vs. Recursion](http://dl.acm.org/citation.cfm?id=317789&dl=ACM&coll=DL&CFID=692159891&CFTOKEN=12249995), page 2.
user76284
<cc.complexity-theory><computability><pl.programming-languages><ho.history-overview>
Why have computer scientists chosen recursor instead of iterator in primitive recursion?
day
# Why have computer scientists chosen recursor instead of iterator in primitive recursion?

(Asked by: username_0 on 2011-06-17)

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?

**Tags:** cc.complexity-theory, computability, pl.programming-languages, ho.history-overview
> **Comments:**
> **username_1**: Primitive recursion was invented before programming.  
> **username_0**: Hmm, so you mean they were not aware of iteration when primitive recursion was invented?  
> **username_2**: 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.  
> **username_3**: See [Type Fixpoints: Iteration vs. Recursion](http://dl.acm.org/citation.cfm?id=317789&dl=ACM&coll=DL&CFID=692159891&CFTOKEN=12249995), page 2.  

---

## 1 answers

### Answer by username_4 on 2011-06-18. Score: 31 | Accepted answer

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.

> **Comments:**
> **username_5**: +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](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2009/) are increasingly relevant these days. In 1960s things were simple; nowadays we have increasingly complicated platforms with memory hierarchies and multiple cores.  
> **username_4**: 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.  
> **username_6**: 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.  
> **username_4**: Most programmers do not write video decoders.  
> **username_6**: 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.  
> **username_4**: I am not being dismissive. I am just stating that when programming is taught to beginners, performance should not come first. This was not so 40 years ago.  
> **username_7**: @AndrejBauer: Amen. Getting this stuff to work right at all is hard enough to begin with.  

---

