Indeed, I haven't met any programmer who couldn't understand recursion when explained in clear terms, same goes for indirect referencing.
If I had to divide the programmers who really understand algorithmic reasoning into two categories, those would be
- A: those who program because it's their job,
- B: those who program because it's their passion.
I believe this grouping is more helpful to explain differences.
https://student.brighton.ac.uk/mod_docs/cmis/past%20papers/c...
You wrote students, while I meant professional programmers. It's not because some people have a tougher time learning those things (whatever the reason can be) that they have no change to get them by the moment they are active professionals.
This said, if I tried to apply your grouping to the people I have been interviewing last year, I would have approximately 100% of them in one category, hence my comment.
Because they are shown examples, instead of taught how, people memorize how to do stuff, instead of learning it from principles.
Take the classic question, recursively reverse a linked list.
You will see a lot of people making false starts, or trying to reverse the list in some way like they would reverse an array, or even repeatedly walking the list to the end.
But if you understand some simple rules about recursion, it's fairly easy to figure out how to do this on the fly. And that is so much better then memorization, because you can explain why you are doing things.
first you are reversing, so you're moving backward, which means you calls your function, then do assignments. If you were doing something moving forwards, like printing in order, you'd print first, then call the function.
Now we need to worry about the end, and the beginning.
First, the beginning, which happens after we have recursively walked the list.
Now, we want to walk to the last node before null, and we need a place to store what we return. so assuming we have something like this in c 'node * recursivereverse(node * current)' and a node structure with next as the next link (we never touch our data)
our test is if (current->next) node * newbeginning = recursivereverse(current->next); else return current; //some assignments go here;
return newbeginning;
Then we just need to figure out the assignments.
Now, people may get tripped up and try to use the new beginning... but then they have to walk it to the end... but the current node already knows the node that comes after it.
so we assign current->next->next = current; IE the node that was previously after the current node now points to the current node as it's next. And that's fine for all the rest of the list, until we get to our original beginning node. We need to worry about the new end.
Since it's going to the end, we need to point it to NULL, otherwise it will point to it's predecessor, meaning we'll have an infinite loop at the end of the last two nodes.
Easy way to deal with it is to just assign the next of the current node to NULL, for each node.
so we add to current->next->next = current; current->next = NULL;
and then you have a reversed linked list. This makes certain assumptions about the list (like it has at least one node, and isn't circular), so don't just copy this for your interview.
So with some simple rules, I figured out how to reverse a linked list. But those simple rules aren't taught, or at least, I came up with them for myself after I became a computer science tutor at my college, because I needed people to understand recursion.
So I guess my point is, it's not that people can or can't understand recursion, it's whether they are taught to think about things in the right way.
Now to a certain extent, we need to teach people to generalize, but if you teach people a general rule (always worry about the beginning and end of any data structure, and that's important for everything, including memory management and debugging) and a recursion specific rule (call the function first to reverse, call the function after to use the current order), and they can generalize.
Too often people come to program with the ability to copy code and get it working (and that isn't anything to denigrate, because it's not simple), but lack the understanding of how to think about things in a deeper way.
static MyLinkedList<T> ReverseLinkedList<T>(MyLinkedList<T> linkedList) { if (linkedList.Next == null) return linkedList;
var newTail = linkedList.Next;
var reversedList = ReverseLinkedList(linkedList.Next);
newTail.Next = linkedList;
linkedList.Next = null;
return reversedList;
}In my mind, a link list is a bunch of nodes with arrows pointing right. To reverse the list, all I need to do is point the arrows to the left.
6(ish) lines of code later, and I've got a recursive reverse method.
Probably because this is similar to the Linux kernel programming style. Many of us learnt C from the kernel or projects that follow it's coding style.
I think of those who understand algorithmic reasoning (i.e. understand loops, assignment, etc.) they also fall into two categories. Those who can understand more abstract programming concepts (indirect referencing, recursion) and those who can't - you can definitely still be a good programer without understanding those but it will limit the areas you can work in.