A discussion about how to understand recursion, especially about the meaning of a base case, was moved here after having hijacked a thread about combinations of items from a list.
I'm 63 years old - been trying to write them off and on for 45 years - still really struggle.
It's on the same cognitive level as trying to imagine viewing a 4D object in 3D space 
Well, on closer inspection ... I exaggerated.
Let me try to be more precise.
In my experience, with a given problem, a recursive solution is often much easier to find and grasp (and more concise) than any non-recursive alternative. This is however a relative thing. So a more correct statement would be:
- "Recursive algorithms are
reallyrelatively easy to write and understand ... once you get the principle."
(the latter part is important too: some people will never grasp it, and that's OK - like some will never grasp math, or enjoy roller coasters, or become proficient at social interactions...)
I still disagree with your revised statement
I get the principle
It's implementing that's hard
I've made quite a few recursive deep mapping/indexing list blocks and EVERY SINGLE TIME each one has been hard to do
And I'm quite bright (if I say so myself)
It's OK to disagree, especially if on subjects related to personal experience.
And I'm definitely not questioning your brightness. 
BTW I found a really interesting video on recursive problem solving on Youtube:
"5 Simple Steps for Solving Any Recursive Problem".
It does actually have some non-trivial examples.
Thx, and may it help and inspire you!
Next time that happens, I would be interested to see your first attempt. Although qw23 is empirically quite wrong about people learning recursion easily (except for mathematicians, who have already learned it under the name "inductive definition"), I think they're probably right to say that if you always find the implementation hard, there's some conceptual misunderstanding at the root of that. And maybe that can be uncovered in your code.
I won't deny these recursive list constructions really tickle my brain in a good way! Last time I felt like this was in Discrete Mathematics class at college. We did learn mathematical induction there. Induction was one of my favorites! For the class as a whole though, induction was really tough, probably the toughest thing all year.
I feel misunderstood 
I never implied learning recursion is easy. All I ‘ve been claiming is that once you grasp the concept of recursion, it is relatively easy to write and understand recursive solutions.
Sorry. Let me try again.
There are different degrees of understanding. For example, I understand how integrated circuit chips are made: You take a silicon wafer, and you etch the places you don't want with acid. You do that with a big silicon wafer, enough for 100s of chips, and then you cut the chips apart, and then you pour epoxy all around them.
But put me in a fab lab and I wouldn't know where to begin.
And so it is, even if less obviously, with software. You should see what the College Board says about recursion in the AP CS A syllabus, and that was written by a committee of computer science professors.
What I'm claiming is that if you can't write recursive procedures, it's because you don't fully understand recursion, even in principle. And so it's fixable by learning whatever piece of understanding is missing.
A few examples of misunderstandings by people who think they understand recursion that show up in their code:
-
Some people don't get that a base case is a perfectly valid argument to the function in itself, not only at the bottom of a stack of recursive calls, and so its return value has to make sense in itself, e.g., it has to be in the range of the function (not necessarily in the domain).
-
Many people don't understand that not all recursive calls are tail recursive. They wouldn't say it that way; what they understand about their (mis)understanding is that they think that when you reach the base case of the recursion, the procedure's work is done. That isn't true in an embedded recursion, still less in a branched (tree) recursion.
-
Some people don't understand that in a function whose domain is lists, the recursive call handles everything except the first item of the list, even the second item. When you see ITEM 2 OF in a student's code, you know this is their problem.
-
The same misunderstanding, looked at from a different angle, can lead to code that mixes recursion and iteration, with a loop that does the whole job, but with a recursive call inside it. (That can be appropriate in a tree recursion, but students do it even in plain linear recursive problems.)
Well, I could keep going forever -- I spent 25 years grading exams in my SICP course. But I hope you get the idea. People with any of those misunderstandings do "grasp the concept of recursion," understanding it maybe 95%, but still what's wrong with their code is based on a misunderstanding in principle.
If I'm understanding him correctly, @cymplecy believes that he has a quirk of mind, a learning disability I guess, that prevents him writing code easily even though he fully understands the idea of recursion. I guess that's possible, but it's never been my experience when I can sit down one-on-one with a student.
(Sometimes students have trouble in a course for reasons of motivation; their parents are making them study computer science but they really want to be a philosopher. But that sort of thing doesn't apply to all you independent learners.)
Is that better?
I obviously don't fully understand how to write recursively
I just saw red when I saw "recursion" and "easy" in the same sentence
Apologies
Simon
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Must not get mad when reading forum posts
Again, I'd be interested to see a nonworking first attempt at a recursive procedure.
Next time I need to make one - I'll shout out
I like your diagnostics of various misunderstandings (or 'thinking errors') that prevent people from constructing a recursive solution for a given task.
I think I am both some people and many people. : - | and I have additionally lots of trouble taking on faith that you deem necessary in order to be able to write one's own recursive program:
Okay, so, for example, here's a really common student error:
This would be a student who's written a zillion MAP-like recursions, in which the return value is a list, and in particular if the input is empty, the block reports an empty list. But LENGTH reports a number -- and the student understands that, because in the recursive case they use + to compute the result. But they wrote the base case code without really thinking about what it means; it's just boilerplate for recursions on lists. Whereas the right thing is to analyze the base case as a legitimate question on its own: What's the length of an empty list? That's what the block should report in the base case.
Here's a more complicated case, because it's about trees, as an example in which reaching the base case doesn't mean the job is complete:
This is a correct procedure (with helper) that reports a list with the same structure as the input (in the example, a list containing a list, a number, and a list) but with the squares of the input numbers.
In reading this code, first you have to understand that a forest is a sequence (a plain list) whose items are trees. (A tree, in this context, is a list of lists to any depth.) This is already a subtlety, because the same list can be thought of as a tree or as a forest! (It's cleaner if we define abstract data types for tree and forest, but more code.)
One way to think about this is that a tree is a two-dimensional data structure, unlike a one-dimensional list of numbers, so to visit every number, we have to move through the tree both horizontally (which is the job of FOREST-SQUARES) and vertically (which is the job of SQUARES itself). So the structure of this program is a mutual recursion, in which SQUARES calls FOREST-SQUARES, and FOREST-SQUARES calls SQUARES.
So, the reason we're looking at this code is to debunk the idea that hitting the base case means the job is finished. This program actually has two base cases, one in each of the procedures. The base case of SQUARES means that we've gotten as far down as we can in this subtree; the base case of FOREST-SQUARES means that we've gotten as far to the right as we can in this forest. So let's instrument the program by logging calls:
So as you see, the program reaches a base case many times before it finally finishes.
Some students believe me about how the structure of the code mirrors the two-dimensional structure of the data (I mean, really believe me, because they understand it, not just accept it because I'm the teacher), whereas other students insist on tracing out the example to make sure that what they expect matches what's in the log. Either way is okay as long as you understand the idea in the end.
If a student doesn't understand about trees, how that manifests itself in their code is that they try to write FOR EACH ITEM loops or, worse, numeric FOR loops to index through the lists, rather than use recursion.
Side note: The structure of FOREST-SQUARES is a MAP-like recursion, in which the recursive call uses ALL BUT FIRST OF the input, and so it can be replaced by a call to MAP:
This structure isn't as simple as it first appears, because the recursive call is inside the function input to MAP, so it happens several times, not just once.
But the object of the exercise here is for me to read your code, not the other way around! :~)
About "take on faith," Gerry Sussman yelled at me for expressing it that way, because he says "faith" means believing something without evidence for it, whereas you're supposed to understand recursion and therefore not have to take anything on faith. And he's right of course: There's nothing magical or supernatural about recursion! I don't mean taking recursion on faith altogether; what I mean is that after you go through a few examples tracing a tree recursion such as SQUARES, for example, the next time you have to write a recursive procedure what you take on faith is that your code for this problem will work on a smaller example. So as you're mentally stepping through an example, you don't also have to step through the recursive call(s). You just compute what the result should be, in your head, and assume (maybe that's a better word?) that that's what your procedure will report.
(...)
It seems you've assumed that I have trouble with your statement itself or at least with your choice of words. However, neither of these is the case.
On the contrary, I find your choice of words quite appropriate since I do have a lot of trouble with taking things on faith, both in real life (which is more troublesome) and also in programming. This is something I need to work on in my life.
Regarding programming, I will chew on what you have written as soon as possible.
I have a feeling I will benefit from your lesson. Tnx.
...
P. S.
(...)
I try to refrain from tiring fellow human beings with by asking them too many questions including those about my choice of words. But Chat-GPT can not get tired. When I asked if 'chew' might be interpreted as having a negative connotation, it replied that 'chew' doesn't have any negative connotation.
P.P.S.
(...)
Having applied the suggested correction generated by Chat-GPT using my favorite prompt, 'Is the following text grammatically correct?', I further asked it to explain why the word 'by' is better than 'with' in the text above. It explained that by using 'by,' a more direct cause-and-effect relationship is conveyed, whereas the word 'with' does not indicate a causative relationship. Pretty awesome, isn't it?
You're welcome!
Using report length of empty_list instead of report empty_list is the correct way to determine the base case in this case, if I understand correctly.
No, that won't work! You can't make a recursive call with the same input you were given. The rule is that a recursive call has to have an input that's closer to the base case: a smaller number, a shorter list, whatever. The reason we need a base case is that you can't keep making recursive calls forever. So it's just report 0.