Why do people have trouble learning recursion?

Question

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.

Answer 1

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

Answer 2

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?

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

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.

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

Didn't this question already get answered?

Why do people have trouble with recursion?

Answer 11

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?"

Answer 12

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.

Answer 13

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.

Answer 14

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

Answer 15

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.

Answer 16

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.

Answer 17

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:

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

More often than:

int hideAndSeek(int count){
    if(count == 0){
        openEyes();
        lookForHiddenFriend();
        return 0;//yeah, zero!
    }else
        return hideAndSeek(--count);
}
closeEyes();
hideAndSeek(100);

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.

Answer 18

Do you understand recursion?

If so, congratulations!

Othwise, click here.

Answer 19

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.

Answer 20

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.

Answer 21

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.

Answer 22

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.

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

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

Answer 27

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.

Answer 28

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

Answer 29

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.