Most programmers learn about loops pretty much at the absolute start of their development experience, where they don't yet have a way to talk about recursion. Don't even start about tail recursion or tail recursion optimisation.
> where they don't yet have a way to talk about recursion.
I'd like to know how its unfortunate as well, I'm not sure I agree with this though.
int a = 0
begin:
if a == 10 {
jump :end
} else {
a = a + 1
jump :begin
}
end:
The programmer will have learnt that programs have a beginning and an end, they will have some notion of a variable, its type, and manipulating their values. They will even likely have learnt conditional branching logic. The only new concept here is that of jumping areas of code.
If you next introduce methods you can clean it up and illustrate it more cleanly:
myFunc(int a) {
if a == 10 {
return
} else {
a = a + 1
return myFunc(a)
}
}
myFunc(0)
Finally you can explain the programmer "hey, there's this shortcut we can take called a loop that expresses this more succinctly":
int a = 0
while (a != 10) {
a = a + 1
}
Nice simple-looking code. Yet this concept requires being able to grok much more than the relatively simple tail-recursive definition.
I suppose the order your introduce those examples in ultimately comes down to whether it's more important for the student to first understand what the computer is doing or how it is doing it.
Most people don't start out thinking like computers, so I think it's probably more important for a new student to understand how code describes a particular series of operations and then help them translate that into how a computer "thinks" about those operations.
I think most people learn about loops before they've learned about functions because your first example maps obviously to your last.
I don't think your middle example would be obvious to most people learning about functions until they've had quite some time to get their heads around what functions do, even with the context of the top piece of code.
> I think most people learn about loops before they've learned about functions
That may be so, however I was taking issue with the idea that they couldn't possibly understand tail recursive functions first. Many (if not all) of the concepts that loops introduce also get introduced with functions (scoping, regions of code, stack parameters, jump return statements e.g. break/return). The programmers just may not have words for all of them with loops, however these concepts are usually explicitly covered with functions.
Loops are particularly useful in applications of batch processing or indirectly for parallelization (again, actually functions are more useful here), so they may learn them for a business use case first, but that doesn't mean they couldn't learn to master both functions and tail recursive variants first. As a sibling commenter pointed out, if you were to come from math's background you might even naturally prefer this construct.
I feel like there's a semi-philosophical question somehwere here. Recursion is clearly a core computer science concept (see: many university courses, or even the low level implementation of many data structures), but it's surprisingly rare to see it in "day to day" code (i.e I probably don't write recursive code in a typical week, but I know it's in library code I depend on...)
But why do you think we live in a world that likes to hide recursion? Why is it common for tree data structure APIs to expose visitors, rather than expecting you write your own recursive depth/breadth-first tree traversal?
Is there something innate in human nature that makes recursion less comprehensible than looping? In my career I've met many programmers who don't 'do' recursion, but none who are scared of loops.
And to me the weird thing about it is, looping is just a specialized form of recursion, so if you can wrap your head around a for loop it means you already understand tail call recursion.
> but it's surprisingly rare to see it in "day to day" code
I rarely use them because I became tired of having to explain them to others, where I've never had to explain a simple while loop that accomplishes the same thing with, usually literally, a couple more lines of code.
From all of my experience, recursion is usually at the expense of clarity, and not needed.
I think it's related to the door memory effect [1]: you loose the sense of state when hopping into the function, even though it's itself.
Not "doing" recursion as a principle is often a sign the person has not been exposed to functional languages or relational kind of programming like Prolog. It often points at a lack of experience with what perhaps is not so mainstream.
Or the person is sensibly trying to make the code easier for other people to understand.
I am tech lead and architect for large financial systems written in Java but have done a bunch of Common Lisp and Clojure projects in the past. I will still avoid any recursion and as people to remove recursion from their PRs unless it is absolutely best way to get readable and verifiable code.
As a developer your job is not to look for intellectual rewards when writing code and your job is not to find elegant solutions to problems (although frequently elegant solutions are the best ones). Your job is taking responsibility for the reliability, performance and future maintenance of whatever you create.
In my experience there is nothing worse than having bright engineers on a project who don't understand they are creating for other less bright engineers who will be working with it after the bright engineer gets bored with the project and moves on to another green field, rewarding task.
The stack traces when something goes wrong are inscrutable under recursion. Same when looking at the program state using debuggers.
Fundamentally, the actual state of the program does not match the abstract state used when programming a recursive function. You are recursively solving subproblems, but when something goes wrong, it becomes very hard to reason about all the partial solutions within the whole problem.
> The stack traces when something goes wrong are inscrutable under recursion.
Hmm. This is a real issue, for the simple case. If tail recursion is not optimized correctly then you end up with a bunch of stack frames, wasted memory...
I propose partially this is a tooling issue, not a fundamental problem with recursion. For tail recursion the frames could be optimized away and a virtual counter employed.
For more complex cases, I'd argue it matters less. Saving on stack frames is still preferable, however this can be acheived with judicious use of inlining. But the looping construct is worse here, as you cannot see prior invocations of the loop, and so have generally no idea of program execution without resorting to log tracing, while even the inlined recusion will provide some idea of the previous execution path.
I don't agree with your last statement. I've been programming forever, and I understand recursion, and I use it, but I never equate it with loops in my mind (unless I'm deliberately thinking that way, like now) and I always find it more difficult to think about than loops.
It is unfortunate, because many programmers develop some feeling of recursion being weird, more difficult or in any way worse than a loop, while this is mostly based on unfortunate language design and lack of familiarity with recursion. It also often comes along with fear of recursive data structures, which is holding programmers back and the products they make.
Most people learning programming have already been exposed to function calling in math (f(x)=x+1). Recursion is not a very big jump semantically from this. Conditional loops are a (relatively) big jump.
I'd be very shocked if anyone past the age of 4 or 5 had never heard (and learned to understand) statements like "Wash your hands until they're clean" which is a conditional loop (wash your hands, check if they're still dirty, repeat if they are, stop otherwise). If a teen or adult learning to program has trouble with conditional loops, I'd be very very surprised. The translation into programming languages (syntax) may be a challenge, the correct logical expressions for their intent may be a challenge, but the concept should not be.
I happen to know (due to job), that many adults have problems grasping for loops (in Python) when learning programming. It is one of the main points where problems arise in programming introductions.
It may all depend on how it is explained for what person, as different people understand different explanations better than others. Or it may be syntax related. Or that people for the first time fathom how they can make the computer do things in such a time saving manner. Who knows.
Most programmers learn about loops pretty much at the absolute start of their development experience, where they don't yet have a way to talk about recursion. Don't even start about tail recursion or tail recursion optimisation.