Lambda the Ultimate

Unfortunately, Eric did not include applications of the Gamma function in his article (I actually used to be the webmaster for Wolfram Research and thus Mathworld when it was taken over -- Eric is a very awesome guy). If you know of any, let me know.

Anyway, this is a series of articles trying to show C programmers that there is more to life than normal imperative programming. It's preceded by articles on higher-order programming, list manipulation, and memory management, and the next one will be on meta-programming.

However, it appears that C has a richer functional tradition than I first thought. Eugenio Vilar showed me how ?: can be used to mimic the nature of many functional programs:

int Factorial (int n)
{
  return ((n == 1) ? 1 :
          (n == 0) ? 1 :
          Factorial(n - 1) * n);
}

-- Learn to program using Linux assembly language

This is abusive, and I'd appreciate it if people not do things of this nature.

Sorry, it's my signature I use pretty much everywhere. If that is considered abusive here, I'm sorry and I'll stop, but you are the first person in any message board or newsgroup that complained.

Saving the day, however, is the fact that I had mistyped the URL in my original signature, and the link does not go where I intended!

Recursion, however, usually utilizes the explicit sturcture of the inductive definition.

The only unintuitive thing, really, is that these definitions can acutally be executed and produce the wanted results. We are simply unaccustomed to this level of epxressiveness...

But, in my experience, there are some cases (in interactive programs - processes) when you have a choice between mutable state and iteration on one hand and referential transparency, recursion AND control operators on the other hand (think callcc, shift/reset, prompt/control, etc.). In most cases this choice is done for you by the language designer (hint: no control operators in Java). So one goes with state and iteration.

The programming in the large issues require further discussion (and were discussed here previously, of course...)

Andris pretty much nails it on the head with the reference to mutable states.

I'd like to add the following points:

1. Recursion introduces variables into a separate scope. This makes it easier to refactor, since it is more apparent what variables are required and what aren't relevant. and has less potential of corrupting another variable that may be used later in a routine. Many times have I hit bugs where I write:

    for customer in customers:
      ...
   

   only to discover I have just clobbered the previous definition of customer.

2. In this regard (of variable scoping), list comprehensions deliver much the same power.

Recursion is much more intuitive.

From dictionary.com:

intuition, n.

1. The act or faculty of knowing or sensing without the use of rational processes; immediate cognition.
2. Knowledge gained by the use of this faculty; a perceptive insight.
3. A sense of something not evident or deducible; an impression.

Such claims (there are several in this thread) are far-fetched.

Recently some individuals made similar claims (i.e., that they found recursion simpler than interation) in comp.lang.prolog. Such people are very much in the minority. Recursion is rarely perceived as intuitive, especially by novices. To claim otherwise is silly and unrealistic. Recursion is taught in college, and usually only in CS courses, and for good reason.

I myself have been writing recursive code for over 20 years, since I was a child, and will frequently choose recursive solutions over iterative ones, but I would still never claim that in general recursion is more intuitive than iteration.

...are an attempt to take a larger problem and divide it up into more manageable chunks. The truly intuitive way to do things is neither iterative or recursive - these are higher orders of abstraction. Rather, it's to lay out the solution in a purely sequential manner.

From the viewpoint of mathematical thinking, I would think think that recursion is a much better fit. But then it depends what maths you are acquanted with. I personally think some problems are more intuitive using iteration and others are more intuitive using recursion. The recursive function for Towers of Hanoi is rather hard to come up with. But then the iterative technique is also not obvious.

The recursive function for Towers of Hanoi is rather hard to come up with. But then the iterative technique is also not obvious.

That's the point! I can't even think of an iterative method that obviously works (though it's easy to invent one that works, but whose reason for working isn't totally obvious, just by fumbling about). Given a problem that lends itself quite naturally to a recursive solution (and uses principles no more complex than "if doing X makes my problem simpler then I should do X"), and where an iterative solution is slightly cryptic, they'll simply find no solution rather than the recursive one.

Recursion isn't intuitive, it's more intuitive. Heck, Computer Science in general isn't intuitive. Just because we are "in the minority" doesn't mean we're wrong either.
And your claim that it is taught only in CS courses is wrong- it's at least taught in Math courses too, where you won't find iteration at all.

Um...'iteration' is a piece of mathematical terminology that plenty of people learn from mathematics courses. Any time an algorithm appears in a mathematics course it's likely to be iterative. For example Newton's method will typically be presented with some pseudocode that looks like a while loop containing a variable assignment (sometimes the variable assignment will be in a modified form like x_{n+1}=f(x_n) rather than x:=f(x)). Out of the people I know who studied mathematics, and didn't spend their time programming (so weren't exposed to recursion as a programming style), many more are familiar with iteration than recursion. I don't think it'd enter their heads to write, say, a dot product between two vectors recursively rather than iteratively. If I showed the recursive approach to this to my non-programming mathematical friends they'd probably thing I was being deliberately perverse.

How do you read a book? You read the first page, and then you read the rest of the book, right?

Recursion rests on the absolutely intuitive idea that the structure of a procedure should follow the structure of the data it consumes (or produces). Inductively defined data leads to recursive procedures. You have to work really hard to avoid it.

After all, there are only two ingredients to recursion (each of which is useful on its own, by the way): breaking a problem into smaller subproblems, and recognizing that some problem is similar to a previous problem. If recursion is not intuitive, then it would seem that one or the other of these ingredients is unintuitive. Since every person I know does both of these things (I know, I know, that's not quite dictionary.com's standard for intuition), I don't buy it.

Intuitiveness is not transitive in the sense that a solution may involve intuitive ideas and yet itself not be intuitive. People who know how to break problems down into smaller ones and who can recognise that a subproblem is similar to a previous problem will consistently fail to find a recursive solution to the Tower of Hanoi problem. It's pretty easy to test. Just go out and grab some random people who haven't been educated explicitly on the subject of recursion and see how long it takes them to solve the problem recursively. You may find that you can even ask highly technical (non-computer scientist and non-mathematician) people and they still won't think of it until recursion is taught to them.

Don't have to write computer programs. They are probably also unable to find a solution to the SICP change problem. And without a formal education, I don't see most people solving integrals and finding a way to solve them 'more intuitive' than another.

...which is that A is intuitive and B is intuitive doesn't imply that something built solely from A and B is intuitive. Maybe you are suggesting that this proposition is true if we restrict ourselves to people who program computers.

We never said recursion was intuitive. Recursion isn't intuitive, it's more intuitive.

So we have

1. recursion is not intuitive,
2. recursion is more intuitive than iteration,
3. Therefore iteration is not intuitive.

So in summary, neither recursion nor iteration are intuitive?!8-))

Kevin Millikin remarks:

How do you read a book? You read the first page, and then you read the rest of the book, right?

Kevin, your penance is to ask 20 persons "How do you read a book?" and report back how many respond with your second sentence above.

My answer would be "You read page 1, then page 2 and so on until you've read the last page." This is akin to what Chris Rathmann said "[the truly intuitive way to do things i]s to lay out the solution in a purely sequential manner."

I also agree with Chris Rathmann when he says "I personally think some problems are more intuitive using iteration and others are more intuitive using recursion." That is, once one understands both iteration and recursion, some algorithms may be more clearly expressed with one or the other.

But I don't believe at all that recursion is intuitive to most people. And my experience is that one must study recursion some time (days at least) and understand the underlying mechanism to some degree before being completely comfortable with it. In contrast iteration can be grasped fully in an afternoon.

So in summary, neither recursion nor iteration are intuitive?!8-))
Yep, and until people stop taking four year courses to learn how to do one or the other and start doing it without any instruction/learning process at all, I think it'll stay that way.
It's also definitely true that some problems are more naturally expressed using iteration. I would simply argue that most are not.

It's also definitely true that some problems are more naturally expressed using iteration. I would simply argue that most are not.

Are you claiming then that the number of problems that "are more naturally expressed using iteration" is finite?

Well, that's not what the study posted here shows.

they're opinion is the same as mine, that the intuitive varies between people - that there may be people more suited to thinking recursively than iteratively. In which case finding recursion more intuitive than iteration is just their apprehension of the relative understandability of the two concepts. The idea further down that a purely sequential way of dealing with the problem is the truly intuitive way of dealing with the problem may be correct, then again it may be perceived as just another preferrence.

Recursion is definately a lot more elegant in many cases. And for those with the right theoretical training, it's also intuitive. But on a basic level it really is not as intuitive as iteration.

Think of a little kid's idea of an algorithm - you have some really dumb human infront of you and you have to tell them how to do something step by step. The intuition is all about giving instructions.

'Keep moving an object from one pile to the other, and adding one to your count, until the pile is empty. Tell me your count'

vs

'Move one object onto the other pile, then count the rest. Add one to the answer and tell me.'

Answer: but you can't tell me to 'count the rest', you haven't finished telling me how to count yet!

It's just not at all intuitive that an instruction to count could be part of the instructions on how to count. Sure, it's for a simpler verison of the problem, but that doesn't help much intuitively. They just see a definition which refers to itself and have to expend a lot of mental effort making sense of that. If they're smart they might end up mentally unrolling the self-referential definition until they convince themselves that it will come to an end at some point, but it's a confusing and roundabout way of phrasing a set of instructions.

In short, we're not born with the concept of fixed-point-combinators built into our brains! it takes insight and practise to formulate and appreciate recursive definitions.

More so than iteration, I mean.
I remember seeing and having trouble with both, but iteration didn't make you think about self-reference ontop of all the other stuff.

Another reason recursion can seem hard: it often requires you to generalise your problem somewhat in order to phrase a recursive solution. Lovely for theorists but not as intuitively obvious if you just want to solve a specific instance. An extra step of abstraction/generalisation.

Trivial example: 'Do this 10 times' vs 'To do this n times, do it once then do it n-1 times. Now let n = 10'.

I would agree with this. I am a fairly novice programmer (Pascal, Java, SAS), and I find iteration more "intuitive" when I am writing code. I believe this is a learned intuition, hoewever, as in most courses, recursion is a one day side trip with a n! example after which it is not mentioned again.

After I have written the iterative code, however, I have recently finding myself going back and re-writing it recursively. I find the recursive solutions tend to be much more "intuitive" to read later on. The code tends to be more compact, and easier to follow, and the method tends to have fewer local variables and a simpler control structure.

Michael

It's already not very unusual to have input syntax different from output one, so why not go further and have different constructs as well?

So, you're a fairly novice programmer and already learning to program in the imperative style of Pascal and Java, learning that recursion is bad, difficult and should be avoided anyway because as we all know it causes stack overflows, ain't it?

How do you suppose recursion would be intuitive, then, when you take it for granted a stateful model of the world, full of program counters, a few limited control structures for looping and lots of preconceipts about the functional model?

As long as Universities teach direct descendants of assembly to students, recursion and higher level programming will never reach a wide audience or be accepted as intuitive practices...

I'm surprised to hear you say that. I interview quite a lot of NCG's in my group, and about 50% of them fail to write a simple recursive algorithm to solve a real problem (such as walk a tree). On the other hand, I've never had an interviewee (is that a word?) failing to solve an iteration problem.

Unnamed studies quoted by my old university tutor apparently showed that students first introduced to recursion considered iteration to be unintuitive, while those introduced to iteration first held the reverse opinion.

That would be what you'd expect, wouldn't it?

Yes, but it's nice to have something more than intuition, because not everyone's intuition is the same.

Perhaps it was this study? Learning recursion as a concept and as a programming technique (ACM).

Two experiments on learning recursion and iteration were carried out. The first studied learning of the mathematical concept of recursion by having subjects compute mathematical functions by analogy to worked out examples. The results suggest that subjects are quite able to induce a computational procedure for both iterative and recursive functions from examples. Furthermore, prior practice with iterative examples does not seem to facilitate subsequent performance on similar recursive problems, nor does prior practice with recursive examples facilitate performance on iterative problems. The second experiment studied novice subjects' comprehension of iterative and recursive Pascal programs. Comprehension of the iterative program was not improved by prior exposure to the recursive version of the program. Comprehension of the recursive version was improved moderately by prior work with the iterative version.

-- Learn to program using Linux assembly language

GOTO and GOSUB are by far the most natural. :-)

Well, I learned INTERCAL first, so COMEFROM is the most natural, clearly.

I think the "intuition" batted about in this thread is closely related to what Van Roy and Haridi call "naturalness" in CTM. Problems whose solutions require a mess of explicit state are more "naturally" expressed using iteration, and problems sans that state (often tree-structured) are more naturally expressed using recursion.

A practical thing about recursion, is that it forces you to deal consciously with termination conditions. You can blunder along for quite a ways with iteration without understanding or being conscious of why your loops terminate (and whether they terminate under the desired conditions). In this sense, recursion has a real engineering advantage over iteration: your code is more likely to be correct.

It's true that most language implementations treat recursion suboptimally, but this situation may improve over time.

In Common Lisp, I frequently mix the two (iteration and recursion), depending on how I perceive what I'm wanting to do. I probably wouldn't use iteration so much though if I didn't have LOOP, which is kind of like every for(;;) loop in every language rolled into one.

The thing about recursion, as far as I know, is that you sometimes need to visualize a stack, in particular when you're coding something that can easily be tail-call optimized. Maybe some cutting-edge languages can translate things so my problem doesn't arise, but in SICP Scheme, oftentimes the tail-call optimization style looks less natural than the ordinary solution I'd write had I not been aware of this optimization concept.

And the difference between recursion and iteration is that the "looping mechanism" is in different places. In some recursions which I find better expressed with iteration, it seems as if the mechanism is mixed unpleasantly with the rest of the code.

I've been fascinated to watch my children learn math concepts, and do think it may have some bearing on this discussion.

My four-year-old has learned can count and add and subtract on her fingers. She can also count collections of other objects, e.g., pennies. She can recognize visually quantities from zero to at least five. (I'd say that's non-recursive and non-iterative).

But with more than that she performs the conventional routine of assigning a correspondence of the next "counting number" to each object in turn. I had her count a line of nine pennies. When she was asked which was the "second" penny, she pointed to the one she had identified with "two". That specific penny was swapped with the one in the middle and she was asked again to point to the "second penny". She again chose the same physical penny that was now in the middle position.

I had a conversation with my six-year-old in which I tried to convince her that there was "no largest number" because you could always add one to get a larger number, and that "infinity is not a number". She had a hard time getting her head around it, and I can't say it doesn't seem a bit metaphysical to me, too.

Although I'm no certainly no expert in cognitive development, I interpret these anecdotes as lending support to the theory that there is some early innate (rhythmic?) capacity that can assist in iterative processes, while grasping something defined recursively (e.g., Peano's axioms) require specific training in symbolic manipulation.

"to recur" is the verb form of the noun "recursion", **NOT** "to recurse".

I'm afraid that this assertion is on thin ice. Just because "recur" and "recursion" share an etymological origin in the same Latin verb does not mean that they must retain an inviolate relationship in English.

To choose a parallel example, "deduce" and "deduct" share the same nominalization, "deduction", and yet have quite distinct uses.

"Recurse" is quite established as a back-formation of "recursion" in the computer science sense, and I see no reason to eliminate it in favour of "recur" which is much more general and potentialy ambiguous and confusing in this instance.

It's not like its "nucular" or something. ;-)