Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In the perils of java schools Joel discusses his experience at Penn and the difficulty of "segmentation faults". He says

[segfaults are difficult until you] "take a deep breath and really try to force your mind to work at two different levels of abstraction simultaneously."

Given a list of common causes for segfaults, I don't understand how we have to work at 2 levels of abstraction.

For some reason, Joel considers these concepts core to a programmers ability to abstract. I don't want to assume too much. So, what is so difficult about pointers/recursion? Examples would be nice.

share|improve this question

closed as too broad by gnat, MichaelT, Dynamic, amon, kevin cline May 8 at 22:39

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

30  
Stop worrying about what Joel might think about you. If you find recursion easy, that's good. Not everyone else does. –  FrustratedWithFormsDesigner Apr 21 '11 at 13:41
6  
Recursion is easy by definition (function that calls self), but knowing when to use it and how to make it work is the tough part. –  JeffO Apr 21 '11 at 13:45
9  
Apply for a job at Fog Creek and let us know how it goes. We're all very interested in your self promotion. –  Joel Etherton Apr 21 '11 at 13:46
4  
@P.Brian.Mackey: We're not misunderstanding. The question doesn't really ask anything. It's blatant self-promotion. If you want to know what Joel is asking about pointers/recursion, ask him: team@stackoverflow.com –  Joel Etherton Apr 21 '11 at 14:06
19  
Duplicate of this question? –  Ozz Apr 21 '11 at 14:36
show 7 more comments

10 Answers

up vote 35 down vote accepted

I first noticed that pointers and recursion were hard in college. I had taken a couple of typical first year courses (one was C and Assembler, the other was in Scheme). Both courses started with hundreds of students, many of whom had years of high-school level programming experience (typically BASIC and Pascal, in those days). But as soon as pointers were introduced in the C course, and recursion was introduced in the Scheme course, a huge number of students--perhaps even a majority--were completely flummoxed. These were kids who had written a LOT of code before and had no problems at all, but when they hit pointers and recursion, they also hit a wall in terms of their cognitive ability.

My hypothesis is that pointers and recursion are the same in that they require you to keep two levels of abstraction in your head at the same time. There's something about the multiple-levels-of-abstraction that requires a type of mental aptitude that it's very possible some people will never have.

  • With pointers, the "two levels of abstraction" are "data, address of data, address of address of data, etc.," or what we traditionally call "value vs. reference." To the untrained student, it's very hard to see the difference between the address of x and x itself.
  • With recursion, the "two levels of abstraction" are understanding how it's possible for a function to call itself. A recursive algorithm is sometimes what people call "programming by wishful thinking" and it's very, very unnatural to think of an algorithm in terms of "base case + inductive case" instead of the more natural "list of steps you follow to solve a problem." To the untrained student looking at a recursive algorithm, the algorithm appears to beg the question.

I would also be perfectly willing to accept that it is possible to teach pointers and/or recursion to anyone... I don't have any evidence one way or another. I do know that empirically, being able to really understand these two concepts is a very, very good predictor of general programming ability and that in the normal course of undergraduate CS training, these two concepts stand as some of the biggest obstacles.

share|improve this answer
4  
"very, very unnatural to think of an algorithm in terms of "base case + inductive case"" - I think it's by no way unnatural, it's just that kids are not being trained accordingly. –  Ingo Apr 21 '11 at 17:54
12  
if it were natural, you wouldn't need to be trained. :P –  Joel Spolsky Apr 21 '11 at 18:01
    
Good point :), but don't we need training in math, logic, physics etc. all of which are in a broader sense most natural. Interestingly, few programmers have any problems with the syntax of languages, yet it is full of recursion. –  Ingo Apr 22 '11 at 9:00
1  
At my university, the first course started out with functional programming and recursion almost immediately, well before introducing mutation and the like. I found that some of the students without experience understood recursion better than those with some experience. That said, the very top of the class was made up of people with a lot of experience. –  Tikhon Jelvis Apr 23 '11 at 9:19
2  
I think the inability to understand pointers and recursion is linked to a) overall IQ level and b) bad mathematical education. –  quant_dev Apr 23 '11 at 10:11
show 2 more comments

Recursion is not just "a function that calls itself." You're not truly going to appreciate why recursion is difficult until you find yourself drawing out stack-frames to figure out what went wrong with your recursive descent parser. Often you'll have mutually recursive functions (function A calls function B, which calls function C, which may call function A). It can be very difficult to figure out what went wrong when you're N stackframes deep in a mutually-recursive series of functions.

As for pointers, again, the concept of pointers is pretty simple: a variable that stores a memory address. But again, when something goes wrong with your complicated data structure of void** pointers which point to different nodes, you'll see why it can get tricky as you struggle to figure out why one of your pointers is pointing to a garbage address.

share|improve this answer
1  
Implementing a recursive decent parser was when I truly felt I had somewhat of a grip on recursion. Pointers are easy to understand at a high level like you said; it is not until you get into the nuts and bolts of implementations dealing with pointers that you see why they are complicated. –  Chris Apr 21 '11 at 17:33
    
Mutual recursion between many functions is essentially the same as goto. –  starblue Apr 21 '11 at 21:10
2  
@starblue, not really - since each stackframe creates new instances of local variables. –  Charles Salvia Apr 21 '11 at 22:29
    
You're right, only tail recursion is the same as goto. –  starblue Apr 22 '11 at 6:21
3  
@wnoise int a() { return b(); } can be recursive, but it depends on the definition of b. So its not as simple as it seems... –  alternative Apr 23 '11 at 1:08
show 1 more comment

Java supports pointers (they're called references) and it supports recursion. So on the surface, his argument appears pointless.

What he's really talking about is the ability to debug. A Java pointer (err, reference) is guaranteed to point to a valid object. A C pointer isn't. And the trick in C programming, assuming that you don't use tools like valgrind, is to find out exactly where you screwed up a pointer (it's rarely at the point found in a stacktrace).

share|improve this answer
4  
Pointers per se are a detail. Using references in Java is no more complicated than using local variables in C. Even mixing them in the way Lisp implementations do (an atom may be an integer of limited size, or a character, or a pointer) isn't difficult. It gets harder when the language allows the same sort of data to be local or referenced, with different syntax, and really hairy when the language allows pointer arithmetic. –  David Thornley Apr 21 '11 at 14:11
    
@David - um, what does this have to do with my response? –  Anon Apr 21 '11 at 14:16
1  
Your comment about Java supporting pointers. –  David Thornley Apr 21 '11 at 15:57
    
"where you screwed up a pointer (it's rarely at the point found in a stacktrace)." If you are lucky enough to get a stacktrace. –  Omega Centauri Apr 21 '11 at 19:38
3  
I agree with David Thornley; Java does not support pointers unless I can make a pointer to a pointer to a pointer to a pointer to an int. Which maybe I suppose I could by making like 4-5 classes that each reference something else, but is that really pointers or is that an ugly workaround? –  alternative Apr 23 '11 at 1:13
show 2 more comments

The problem with pointers and recursion is not that they're necessarily hard to understand, but that they are taught badly, especially with respect to languages like C or C++ (mainly because the languages themselves are being taught badly). Every time I hear (or read) someone say "an array is just a pointer" I die a little inside.

Similarly, every time someone uses the Fibonacci function to illustrate recursion I want to scream. It's a bad example because the iterative version is no harder to write and it performs at least as well or better than the recursive one, and it gives you no real insight into why a recursive solution would be useful or desirable. Quicksort, tree traversal, etc., are far better examples for the why and how of recursion.

Having to muck with pointers is an artifact of working in a programming language that exposes them. Generations of Fortran programmers were building lists and trees and stacks and queues without needing a dedicated pointer type (or dynamic memory allocation), and I've never heard anyone accuse Fortran of being a toy language.

share|improve this answer
    
I will agree, I had had years/decades of Fortran before seeing actual pointers, so I had been using my own way of doing the same thing already, before being given the chance to let the lanquage/compiler do it for me. I also think C syntax regarding pointers/addresses is very confusing, even though the concept of a value, stored at an address is very simple. –  Omega Centauri Apr 21 '11 at 19:44
    
if you have a link to Quicksort implemented in Fortran IV, I'd love to see it. Not saying that it can't be done -- in fact, I implemented it in BASIC some 30 years ago -- but I'd be interested to see it. –  Anon Apr 22 '11 at 20:43
    
I never worked in Fortran IV, but I did implement some recursive algorithms in the VAX/VMS implementation of Fortran 77 (there was a hook to allow you to save the target of a goto as a special kind of variable, so you could write GOTO target). I think we had to build our own runtime stacks, though. This was long enough ago that I can't remember the details anymore. –  John Bode Apr 22 '11 at 21:01
add comment

There are several difficulties with pointers:

  1. Aliasing The possibility of changing the value of an object using different names/variables.
  2. Non-locality The possibility of changing an objects value in a context different from the one in which it is declared (this also happens with arguments passed by reference).
  3. Lifetime Mismatch The lifetime of a pointer may be different from the lifetime of the object it points to, and that may lead to invalid references (SEGFAULTS) or garbage.
  4. Pointer Arithmetic. Some programming languages allow the manipulation of pointers as integers, and that means that pointers can point anywhere (including the most unexpected places when a bug is present). To use pointer arithmetic correctly, a programmer must be aware of the memory sizes of the objects pointed to, and that's something more to think about.
  5. Type Casts The ability to cast a pointer from one type to another allows overwriting of the memory of an object different from the one intended.

That's why a programmer must think more thoroughly when using pointers (I don't know about the two levels of abstraction). This is an example of the typical mistakes made made by a novice:

Pair* make_pair(int a, int b)
{
    Pair p;
    p.a = a;
    p.b = b;
    return &p;
}

Note that code like the above is perfectly reasonable in languages that don't have a concept of pointers but rather one of names (references), objects, and values, as functional programming languages, and languages with garbage collection (Java, Python) do.

The difficulty with recursive functions happens when people without enough mathematical background (where recursiveness is common and required knowledge) try to approach them thinking that the function will behave differently depending on how many times it has been called before. That problem is aggravated because recursive functions can indeed be created in ways in which you do have to think that way to understand them.

Think of recursive functions with pointers being passed around, like in a procedural implementation of a Red-Black Tree in which the data structure is modified in-place; it is something more difficult to think about than a functional counterpart.

It's not mentioned in the question, but the other important issue with which novices have difficulty is concurrency.

As others have mentioned, there is an additional, non-conceptual problem with some programming language constructs: it is that even if we understand, simple and honest mistakes with those constructs can be extremely difficult to debug.

share|improve this answer
    
Using that function will return a valid pointer but the variable is in a scope higher than the scope that called the function, so the pointer could (assume will) be invalidated when malloc is being used. –  rightfold Apr 21 '11 at 19:39
4  
@Radek S: No, it won't. It will return an invalid pointer that on some environments happens to work for a while until something else overwrites it. (In practice, this will be the stack, not the heap. malloc() is no more likely than any other function to do so.) –  wnoise Apr 22 '11 at 6:56
1  
@Radeck In the sample function, the pointer points to memory that the programming language (C in this case) guarantees will be freed once the function returns. Thus, the returned pointer points to garbage. Languages with garbage collection keep the object alive as long as it is been referenced in any context. –  Apalala Apr 22 '11 at 21:38
add comment

Pointers and recursion are two separate beasts and there are different reasons that qualify each as being "difficult".

In general, pointers require a different mental model than pure variable assignment. When I have a pointer variable, it is just that: a pointer to another object, the only data it contains is the memory address that it points to. So for instance if I have an int32 pointer and assign a value to it directly, I'm not changing the value of the int, I'm pointing to a new memory address (there are a lot of neat tricks you can do with this). Even more interesting is having a pointer to a pointer (this is what happens when you pass a Ref variable as a function Parameter in C#, the function can assign an entirely different object to the Parameter and that value will still be in scope when the function exits.

Recursion takes a slight mental leap when first learning because you're defining a function in terms of itself. It's a wild concept when you first come across it, but once you grasp the idea, it becomes second nature.

But back to the subject at hand. Joel's argument isn't about pointers or recursion in and of themselves, but rather the fact that students are being removed further from how computers really work. This is the Science in Computer Science. There is a distinct difference between learning to program and learning how programs work. I don't think it's a matter so much of "I learned it this way so everyone should have to learn it this way" as him arguing that many CS programs are becoming glorified trade schools.

share|improve this answer
add comment

I give P. Brian a +1, because I feel like he does: recursion is such a fundamental concept that he who has the slightest difficulties with it should better consider looking for a job at mac donalds, but then, even there is recursion:

make a burger:
   put a cold burger on the grill
   wait
   flip
   wait
   hand the fried burger over to the service personel
   unless its end of shift: make a burger

Surely, the lack of comprehension has also to do with our schools. Here one should introduce natural numbers like Peano, Dedekind and Frege did, so we would not have so much difficulties later.

share|improve this answer
6  
That's tail recusion, which is arguably looping. –  Michael K Apr 21 '11 at 14:33
6  
Sorry, to me, looping is arguably tail recursion :) –  Ingo Apr 21 '11 at 14:34
3  
@Ingo: :) Functional fanatic! –  Michael K Apr 21 '11 at 14:37
1  
@Michael - hehe, indeed!, but I think one can make the case that recursion is the more fundamental concept. –  Ingo Apr 21 '11 at 14:41
    
@Ingo: You could, indeed (your example demonstrates that well). However, for some reason humans have a hard time with that in programming - we seem to want that extra goto top for some reason IME. –  Michael K Apr 21 '11 at 14:53
show 1 more comment
  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

The concept of self referential data and code underlies the definition of pointers and recursion respectively. Unfortunately, widespread exposure to imperative programming languages has led computer science students to believe that they must understand the implementation via the operational behaviour of their runtimes when they ought to trust this mystery to the functional aspect of the language. Summing all the numbers up to a hundred seems a simple matter of starting with one and adding it to the next in the sequence and doing it backwards with the aid of circular self referential functions seems perverse and even dangerous to many not used to the safety of pure functions. Past experience with imperative languages has burnt them and the desire to comprehend all the intervening states is driven by a suspicion that variables are subject to change even if they grasp that the same name doesn't refer to the same thing when a function is invoked again from within itself.

The concept of self modifying data and code underlies the definition of objects (i.e. smart data) and macros respectively. I mention these as they are even harder to understand especially when an operational understanding of the runtime is expected from a combination of all four concepts - e.g. a macro generating a set of objects that implements a recursive decent parser with the aid of a tree of pointers. Rather than trace the entire operation of the program's state step-by-step through every layer of abstraction at once, imperative programmers need to learn to trust that their variables are only assigned once within pure functions and that repeated invocations of the same pure function with the same arguments always yields the same result (i.e. referential transparency), even in a language that supports impure functions as well, like Java. Running around in circles after the runtime is a fruitless endeavour. Abstraction should simplify.

share|improve this answer
add comment

I disagree with Joel that the problem is one of thinking at multiple levels of abstraction per-se, I think it's more that pointers and recursion are two good examples of problems that require a change in the mental model people have of how programs work.

Pointers are, I think, the simpler case to illustrate. Dealing with pointers requires a mental model of program execution that accounts for the way programs actual work with memory addresses and data. My experience has been that often times programmers haven't even thought about this before they learn about pointers. Even if they know it in an abstract sense, they haven't adopted it into their cognitive model of how a program works. When pointers are introduced it requires a fundamental shift in the way they think about how the code works.

Recursion is problematic because there are two conceptual blocks to understanding. The first is at the machine level, and much like pointers it can be overcome by developing a good understanding of how programs are actually stored and executed. The other problem with recursion is, I think, that people have a natural tendency to try to deconstruct a recursive problem into a non-recursive one, which muddies the understanding of a recursive function as a gestalt. This is either a problem with people having an insufficient mathematical background, or a mental model that doesn't tie mathematical theory to the development of programs.

The thing is, I don't think that pointers and recursion are the only two areas that are problematic for people stuck in an insufficient mental model. Parallelism seems to be another area that some people simply get stuck at and have difficulty adapting their mental model to account for, it's just that often times pointers and recursion are easy to test for in an interview.

share|improve this answer
add comment

Very similar to Anon's answer.
Aside from cognitive difficulties for newbies, both pointers and recursion are very powerful, and can be used in cryptic ways.

The downside of great power, is they give you great power to screw up your program in subtle ways.
Storing a bogus value into a normal variable is bad enough, but storing something bogus into a pointer can cause all sorts of delayed catastrophic things to happen.
And worse, those effects may change as you attempt to diagnose/debug what is the cause of the bizarre program behavior.

Similarly with recursion. It can be a very powerful way to organize tricky stuff -by stuffing the trickiness into the hidden data structure (stack).
But, if something is done subtlely wrongly, it can be hard to figure out what is going on.

share|improve this answer
add comment

protected by gnat May 6 at 11:22

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.