Why recursing is better than looping

I just posted a new article for imperative-loving people about why recursive programming is better than imperative programming.

Here's the article: Mastering Recursive Programming

I thought you all might be interested, and I am interested in any comments, criticisms, additions, subtractions you all have.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Just one thing

In the factorial example you say that the idea of factorial doesn't make sense for numbers less than one. The basic notion of factorial comes from the number of permutations of a given number of items. Since zero items can be arranged in one way, 0! has been defined as 1 for quite a while (and it does make sense). For negative integers, your statement is correct, although the gamma function can also be used as a suitable extension of the factorial to non-integral elements of both the real and complex domains.

That being said, I probably shouldn't pick the nits when the message - that recursive programming is a good thing - is a good one and is shown pretty well :-).

Great info

Someone else had pointed out the 0! thing, but I had not heard of Gamma functions (in fact, my mathematical knowledge is really lacking in general -- mostly because I abhor mathematical notation).

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);
}
Giving it the form we normally expect in a functional language.

-- Learn to program using Linux assembly language

Ads

Is that an ad at the the bottom of your post?!

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

Sorry

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!

Another issue

At the end of the article you claim that iteration is more intuitive than recursion. I would dispute this. I find recursion far more natural and simple than iteration. Iteration is perceived as intuitive precisely because most learn in their introductions to Computer Science. But if more curricula introduced students to computer science with books like The Little Schemer or even SICP/CTM, it would likely seem the other way around. Otherwise a nice article.

Indeed

Recursion is much more intuitive. To understand iteration, indeed - to express it formally, you quite often need auxilary variables. Variables such as loop indexes are hardly intuitive, as anyone who has taught introductory programming courses knows.

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

Almost agree

Recursion is more manageable, probably because it befriends referential transparency, while iteration requires some mutable state (loop indices).

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.

Sure

I don't really think that recursion is *always* the most intuitive way to structure your code. But, intuition is about what seems more natural, which is why I mentioned people with no prior programming experience.

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

Mutable state

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.

Comments Out of Touch With Reality

Ehud Lamm wrote:
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.

You took the words out of my mouth!

A pretty simple demonstration of just how unintuitive recursion can be is to show novices, or computer non-experts, the recursive solution to the Tower of Hanoi problem. Many will have a lot of trouble grasping it even though the recursive solution is nothing other than reducing the problem to a simpler version of itself. Additionally, even though the recursive solution is incredibly simple to describe, extremely few people will figure it out for themselves without coaching in recursion. Recursion simply doesn't come naturally.

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.

Both recursion and 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

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.

We never said recursion was intuitive

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.

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.

Silly and unrealistic?

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.

See my comments on the Tower of Hanoi.

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.

People on the street..

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.

This isn't really addressing my point...

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

Is Recursion More Intuitive Than Iteration?

Jeff Cutsinger remarks:
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.

yep

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.

yep

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 stu

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

perhaps

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.

Not intuitive

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 mea

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 a

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

Writers/readers

So it sounds like iteration is more intuitive for writing, while recursion for reading? Then the logical conclusion would be to use computer for routine task of translating the former into the latter :-)

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?

Java, Pascal

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

Indeed?

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

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.

Not very surprising

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

Yes, but it's nice to have so

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

Study

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.

Same or Different Problems

I'm curious if they covered the same or different classes of problems in the material. If it is the same, then I would take the study at face value -- learning recursion is just as hard/easy as learning iteration. However, if they gave recursive problems to the first group (i.e. problems which don't require using accumulators and other sorts of auxiliary parameters) and more iterative problems to the second group (i.e. problems that do), then the results of the study may just simply be that learning recursion on things naturally recursive is just as easy as learning imperative on things that are naturally imperative.

-- Learn to program using Linux assembly language

I learned Apple II Basic first.

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

INTERCAL

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

Intuitive .eq. natural?

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

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.

shampoo, or envelopes?

Infinite loop: Lather, rinse, repeat.
Infinite recursion: To seal, moisten, fold, and seal.

They seem about equally intuitive to me. :-)

nice discussion...

... but i think they are two sides of the same coin.

Child Development

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.

That does it for me.

"Split it into smaller pieces and solve them" - if you say this to people who are not developers/computer scientists, etc., they will often evince confusion. I know that I did at first hearing. On the other hand, do the first then, then the second thing, then the third... is familiar from everyday life. It does take some thinking and study to understand recursion.

That said, recursion offers such an immensely powerful way of thinking about problems that I say:
"Who cares if recursion is not intuitive?"

Curses to "recursing"

"to recur" is the verb form of the noun "recursion", **NOT** "to recurse". Sorry, one of my pet peeves :(

Gong!

"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. ;-)

Recursion was much less intuitive than iteration in my course

When I was a student, I remember how difficult recursion was in contrast with simple looping. People immediately got the 'FOR I = 1 TO 10' thing, but recursion created very big difficulties for almost all of us.

Of course recursion is one of the foundamental concepts, and it should be one of the first things tought, but it's hardly more intuitive than iteration.

Fold!

Surely the best way to do looping is to avoid it altogether? Let container authors provide methods for efficiently iterating over their contents (e.g., via map, fold, filter etc). The most intuitive way to describe reading a book is neither "read the first page, then read the rest of the book", nor "read page 1, then page 2, ..." -- rather, it is simply "read every page": book.map(readPage)! No stinking loops! :-)

Incidentally, I hear that "re

Incidentally, I hear that "recursion" was used to refer to any time a function called another function (or itself). Eventually it referred to the special case of a function eventually calling itself during its own execution.

I actually prefer the old version; I find it much more enlightening.