As per the title. Why do people have a hard time grasping a function that calls itself? It took most of my friends a week or two to get it.

+10  A: 

Perhaps it isn't the idea that a function can call itself, but rather understanding when that might actually be useful and appropriate.

In my experience, most developers can identify a situation where recursion could be useful... but getting it to work is their problem. The exception is Scientific Computing developers. Recursion isn't in their vocabulary.
James Schek

It's not difficult in theory.
In practice it can be a little tricky, what happens if you allocate memory, does that static variable change, how do you track how many deep you are, how do you escape form all of them in an error?

Martin Beckett

I'm sure that, given enough time to work it through the grey matter, and a good explanation of what is actually going on, anyone could understand it. It's most likely down to our orientation as developers; some people struggle for ages to understand pointers in C whilst some people get it straight away.


I think the hard part is learning to solve problems in a recursive way. Ages ago, I worked on the "Knight's Tour" for quite a while, and then the bulb went off brightly on my head. I had probably seen the syntax for several hours in class and thought that I understood.

Michael Easter
+4  A: 

Because brain, the thing in our heads we use, is used to completing one thought before starting another. It doesn't lend itself well to start thinking about the same thought before you have finished thinking about that thought and in the end wrapping it all up from the thoughts you have been thinking but not finished because you were thinking about it more deeply.

Many people are just not used to think like this. :)

"Because brain, the thing in our heads we use, is used to completing one thought before starting another." Not so much with females... (it's science, look it up.)
And besides, doesn't the "top-down" approach to design kind of void that point anyway?
Sure. Female programmers. You almost had me, almost! ;p
Damn... Next time... muwahahaha
+1  A: 

I see this all of the time in programmer interviews. Joel wrote about it a while back

Interestingly, recent grads seem to understand it better. Maybe because you study it in school, but many programmers don't use it enough afterward. I see a lot of accomplished developers struggle with it.

Lou Franco
I reckon it depends on what kind of programming one does and the frequency with which recursion is used. It's sort of like a cool tool you buy, like a big ol' pipe wrench, that you love to use when you get a chance, but there just aren't that many chances unless you're a plumber. Or something.
+15  A: 

People have trouble with recursion because people have trouble with recursion. :-)

Sherm Pendley
People have trouble with recursion because they often confuse it with iteration.
Ed Guiness
iteration is really a special case of tail-call recursion, so i can see why they'd confuse it, since they are kinda the same thing..?
Indeed, Claudiu.
+5  A: 

Back in university when they were bashing the idea about recursion into our heads, the folks who didn't get it usually had a common problem: how do you stop the recursion?

It seems simple, but some people have a hard time trying to figure out how to write a method that can call itself but also stop at the right time and return the appropriate values.

Also, as quip mentioned, knowing WHEN to use recursion seems to be an issue ;)

Jay S

I think this is because, generally, people are taught to think linearly when it comes to language. Holding a stack of state in one's head and drilling down and working your way back is not natural. It is not terribly difficult once you get the hang of it but not the way people tend to operate throughout their day. To remind yourself why it is hard try to learn something new and unusual but not difficult like Bayesian Inference.

fyi, you're missing the 'e' on your link to the wikipedia article
Richard Levasseur
+85  A: 

Didn't this question already get answered?

Why do people have trouble with recursion?

Nice (see my comment on this!)
LOL! I clicked the link twice, i thought it was a typical browser hickup ... :)
This truly deserves to be the selected answer.
Ed Guiness
Oh, I get it. Took a second or two. But then, I've always had trouble with recursion.
Of course that approach will lead to stack overflow ...
Dave DuPlantis
I hope you guys will all vote up this answer, and vote up the question so more people can enjoy (and vote up) this answer.
The dictionary definition of Recursion - Recursion: See Recursion.
J Francis
Very Clever! lol!
Gary Willoughby
Who marked this offensive? O.o
This is awesome.
Ryan Guest
+1 for receiving +1
This answer has already been given: ;)
Why do people have a hard time grasping a StackOverflow answer that links to itself? It took most of my friends a week or two to get it.
+18  A: 

At least two reasons: the first is that recursive processes aren't really talked about / taught in primary school. You'd be astonished if today people didn't get a concept like zero or Cartesian coordinates, but not too many hundreds of years ago, these were advanced concepts.

The second reason is that to understand a recursive function you have to mentally model the stack: you have to understand that the 'x' you're looking at is not the 'x' the first time through. With an iterative loop, that's a little easier to get because you have a nice handy i = 0, i = 1 assignment to answer "why are these values different?"

Larry OBrien
This is an excellent answer, vote up.
+23  A: 

Some recursive functions are easier to understand than others. A recursive version of the fibonacci function is pretty easy to understand and reason about.

Some things that contribute to the difficulties in grasping recursive functions include:

  • Making sure the function terminates.
  • How to achieve tail-recursion (if it's supported by your language).
  • Mutually Recursive functions (e.g. A calls B, B calls A, etc.).
  • Dealing with multiple levels of complex context. You can easily find yourself wondering how you got to where you were.
  • Some recursive functions combine their results in complex ways.

EDIT: I'm not condoning the use of recursion to calculate Fibonacci sequence.

Tim Stewart
Fibonacci is the worst use ever for recursion. It's exponentially slower than an iterative implementation.
Serge - appTranslator
It's also a good explanation for recursion, because we almost always define the sequence as "a sequence starting with 0,1 where each element is the sum of the previous 2 elements"
Actually, when I was starting to learn recursion, I didn't find it that hard at all, but when I saw the fibonacci recursion, I couldn't understand why it worked, it seemed like magic.
hasen j

One does not understand recursion by mere explanations.

One has to step through a recursive function in a debugger to understand how it actually works.

You cannot be... Told what recursion is. You have to see it for yourself.
that's an unfounded generalisation. i happen to understand better from theory than from stepping.
Was that an attempt at a "Matrix" joke, Trauma? I guess you have to take the red pill to understand recursion. =)
+1  A: 

Probably because the notion of solving Xby solving a solving a slightly modified version of X and then rolling up the changes is a strange proposition...

But then again, maybe it isn't!!!


The concept of recursion is somewhat mind-bending, and I'm not ashamed to admit that. However, syntactically, it's fairly simple to implement. Is that a fair statement?

So, like regular expressions, you should know what you're doing.


I think people are often wary of recursion, and rightly so in many cases, because for many alogorithms the amount of overhead on the stack is unknown and data dependent, and as such a principal cause of stack overflows. For this reason, if there is an option between a recursive function and an iterative function, it often makes more sense to go with the iterative solution. Alternatively you are left with adding reference counting stack guards in place, which sometimes kills the elegance of the recursive solution.

Shane MacLaughlin
+2  A: 

When I first learnt programming I had trouble with recursion too. It probably has to do with it being a new concept, in the sense that there is no "real life" analogue (at least most people I know don't do things in their lives based on recursive algorithms).

What I mean:
Real life hide-and-seek:

Close your eyes and count down from a hundred. Then, open your eyes and try to find where your friend is hiding.

The programming analogue is understood as:

for(int i = 100; i >= 0; i--);//or using "while" variation

More often than:

int hideAndSeek(int count){
    if(count == 0){
        return 0;//yeah, zero!
        return hideAndSeek(--count);

Admittedly the example is very contrived and ugly. But the point I want to make is that most people do not naturally think in terms of functions in real life, but rather think in a way that is closer in concept to a while/for loop.

Exactly. While I did not have trouble with it personally I have had enough trouble explaining recursive things to others that I see where it comes from.
Loren Pechtel
+5  A: 

Do you understand recursion?

If so, congratulations!

Othwise, click here.

There's a thought - teach recursion using the metaphor of web browser history.Do mathematicians have trouble 'getting' proof by induction ( P(n) is true if P(n-1) is true and P(0) is true) )?
Pete Kirkham
I was going to make that joke!
+2  A: 
6eorge Jetson
+3  A: 

I think learners find recursion difficult for two reasons.

First, the teacher usually prefaces the topic of recursion with the words "This will be difficult," thereby setting up the students to believe exactly that.

Second, the typical recursive problems (Fibonacci, factorial, Towers of Hanoi, etc.) are so abstract and contrived that students have a hard time grasping why recursion would be useful, especially when the teacher also shows the iterative solution that's much easier.

Recursion can be successfully taught when recursion is the solution that occurs most naturally to the programmer. For example, descending into a directory tree or sorting by using a divide-and-conquer algorithm. If you can convince the student that a list is simply a head element followed by another list, then recursive solutions to list-oriented problems are also easy to visualize and program.

At the early stages of learning, it also helps to use a programming language in which recursion is a natural algorithmic structure. Think: functional languages.

I love how Haskell uses pattern matching to define factorial in an almost declarative manner:

fac 0 = 1
fac n = n * fac (n-1)

If that's not a straightforward, recursive definition of factorial, I don't know what one is.

Barry Brown
What I find funny about the haskell version, is the thought of what happens if I ask for fac (-1)
Good point, gnud, but it really isn't difficult to fix with a guard pattern. Just add a case for "fac n | n < 0 = undefined".
Doug McClean

People have trouble learning recursion because they don't understand recursion.

To understand recursion you must first learn it.

The difficult lies in finding the base case, where despite having trouble learning it you learn it anyway. You just need to go with smaller and simpler examples.


I'd add an instance where, in my teaching experience, recursion was found especially problematic by students: that is, where a (recursively defined) function calls itself more than once, as in merge-sorting or other sorting algorithms. The typical questions are of the kind "But in which order have I to / do the computer execute them?" "Does everyithing happen simultaneously?" and the like.


Having taught it, it is what I call a "speed bump" concept - something you gotta slow down and deal step by step while the brain builds a new framework.

You start with simple math functions, walking through them cycle by cycle.

Then in data structures you use them for tree-walking, again step by step, always paying attention to the stack of callers and the local variables and parameters at the levels above.

Other speed bumps: arrays and sequential files. Experienced programmers take these for granted, but if they are new to you they are something you have to slow down and crawl over before you "get it".

Edit: And as DaG said, new programmers even have trouble with the idea that computers don't just "do everything at once" (and read your mind while they're at it).

Edit: It helps if the student is doing a project that pretty much needs recursion, so they can struggle with how to do the problem and start inventing it on their own. They start asking if they should call another routine just like the one they've already got. Then you tell them that's what "recursion" is for, and you should just see them light up.

Mike Dunlavey
+1  A: 

Recursion is related to mathematical induction. The correctness of a recursive function is usually proven by mathematical induction. To many people, mathematical induction is just circular reasoning. I'm sure there are people with no trouble with recursive functions have serious problem with mathematical induction.

+1  A: 

I've often wondered if the reason some people have trouble with recursion is because they fail to realize that you can have multiple instances of the same function, each of which is separate from other previously-called instances. This could be explained in the following way:

  • You can have a blueprint that describe the structure of a house, and then build multiple houses from that one blueprint. Each house is unique, with different people living in them, but they all share the same floor plan.

  • When writing a function, you are basically writing a "blueprint" of how a function of that type behaves. When you call that function, you get a unique instance that has its own unique local variables and input arguments, but it performs the same algorithmic operations as all the other instances.

I'm curious if part of the difficulty in understanding recursion lies with the incorrect notion that calling a function from itself means you are re-entering the same function from the beginning, maintaining the same values that all the variables previously had.


Because they haven't read Gödel, Escher, Bach: An Eternal Golden Braid, and don't speak German. Seriously though, it's difficult to keep track, not so much going down, but going back up, and visualizing the unraveling of the "braid", if you will. Since you have to keep track of where you are at, but everything looks the same at that level, except perhaps some variables, you can get lost, forgetting where you actually are. So perhaps it's mainly a short-term memory issue.

Richard Hein
+1  A: 

Because: "In order to understand recursion, one must first understand recursion." ;-)

instant nirvana

I think peolple approach it tentatively if they've never used it before since if it is mishandled, it is the very definition of infinite loop. Probably people think about using it, give it a try, have some problems, then use something else instead. But once I got it, I used it much more frequently.

+2  A: 

It's hard to grasp because often recursion is misunderstood by beginning CS students to work like a goto. In other words, rather than generating a new stack frame, it's pretty natural to expect the code to simply jump to the entry point of the function, rather than creating a new set of local variables with each recursive call.

That's why when I teach recursion I first walk the students through an example of how (non-recursive) function calls work, explicitly drawing the stack at each step. Once they've got a handle on that, it's not too big a leap to replace "function A calls function B" with "function A calls function A".

Caffeine Coma

When I first was learning to program, recursion was both easy and hard to understand.

Easy, because we were studying Lisp, which lends itself to recursion naturally.

Easy, because I used to solve word puzzles with backtracking approaches, hence thought recursively.

Hard, because at the same time I was learning recursion I was also learning about scoping rules, and pass by reference versus pass by value. For recursion to work, certain data must be passed by value. But I did not know that arrays were different than other types in Lisp and were passed by reference, hence were not being copied, which screwed up the algorithm.

Hard, because I had to write a look ahead algorithm for a game (like Othello) where player A wants his best move but B's worst move, and vice versa and it was hard to wrap my mind around how to toggle the evaluation function to work oppositely depending upon whether the stack depth was odd or even.

Hard, because you need to learn that many recursive algorithms must be set up with an initial function which then calls the recursive part as a separate function.

Paul Chernoch