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.
Simply reporting 0 was my first intuition, but the intuition was overridden by my reason because it appeared to be too simplistic.
I then started thinking about what else it could be, and in front of my eyes, the primitive length of block appeared as the solution. I completely forgot that the primitive block is the same block we are trying to construct from scratch using recursion here.
P. S.
Could the recursive case be expressed without using the all but first of block, for example by using (((length of data) - 1) +1) or I am wrong?
Nope, sorry. Even though you're wrapping some arithmetic around it, your recursive call is (LENGTH OF DATA), i.e., the same input you were given, not one closer to the base case. (And anyway, subtracting 1 then adding 1 doesn't change the result!)
After re-reading this section several times, it seems to me that what you have been trying to say is that it is more complicated because it's about a two-dimensional process as you have explained further down in the text. (Maybe to a mathematician it is obvious that a tree is a two-dimensional data, but it is not to me as a non-mathematician.)
However, I do understand now why the recursive process needs to reach both base cases (i.e. on both dimensions) and that even if it reaches a base case on one of the dimensions, but not yet simultaneously on the other dimension, that the process should not stop.
Aha, it has now downed on me that in order to reach a base case, the (remaining) piece of the data that the recursive 'hammer' is hitting should be 'reduced' each time the 'hammer' is called, and that this reduction is achieved by an all but the first of block.
If I understand correctly, the block thus have a crucial role, as a main character in a movie.
No, that's not how it works. For one thing, the horizontal base case is that the input is an empty list, but the vertical base case is that it's a number. It can't ever be both of those at once.
The point about the base cases is that when you reach one, either one, the odds are you're not done with everything. You're in the middle of the tree, and the code has to remember somehow what it has still to do. The way it remembers is implicit in the stack of procedure calls. Each procedure has a continuation that says what the program still has to do, just what we need. (I'm not saying that the user's code will make explicit reference to continuations with CALL W/ CONTINUATION. Just that when a procedure call REPORTs something, Snap! has to know which procedure is waiting for this report, and it does know.)
Yes, exactly. It isn't always ALL BUT FIRST, but that's the usual thing if the input is a list. If the input is a number, it'll probably be INPUT−1. But if you're writing a program to translate a word to Pig Latin, the input in the recursive call is "a word with the same letters, but with the first vowel one step closer to being the first letter of the word."
What I see in the picture is SQUARES procedure, not FOREST-SQUARES. Am I missing something?
In either case, I don't find it simple. It does look elegant and terse, but in fact it is so 'dense' that I can not see through it. It's impenetrable to my non-mathematical mind.
The SQUARES / FOREST-SQUARES thing was apparently just for logging and showing the steps of the SQUARES recursion process in the first place. I suppose @bh made an error while using the “FOREST-“ prefix in his most recent post.
The reason SQUARES is this concise (or terse, if you prefer) is that it basically does something truly simple: in a “tree” made of branches (lists) and “leaves” (numbers), all numbers (leaves) are squared, and the branches (including sub-branches, sub-sub-branches, and so on) are traversed to find any leaves.
It may be a lot of work, but it's not complicated
... just like you will get out of even the vastest of mazes by simply keeping right all of the time (provided it's a 2D-maze, without "islands")
The “trick” is that each element of the tree is itself considered a separate (smaller!) tree. Such tree may be a single leaf (= number), or perhaps consist of millions of elements, or anything in between.
So you subdivide your problem into ever smaller problems, and each and every one of them will lead you to a base case … that you already solved.
The “leap of faith” it takes is that each sub-problem is indeed closer to a solution.
Perhaps you are intimidated by the MAP (SQUARES ()) OVER (tree) part. What it means is you take each element of the list (as tested before) that is the current tree, and apply the SQUARES function to it (= each element of the current tree is itself considered a tree, and processed accordingly).
Hope this helps.
What I said was,
My original SQUARES ends with
REPORT (FOREST-SQUARES (TREE))
The one in the picture you're talking about ends with
REPORT (MAP (( SQUARES () )) OVER (TREE))
So my point was that the call to FOREST-SQUARES can be replaced with a call to MAP.
The trouble with teaching in this medium is that I can't read your body and so I tend to say too much. Maybe I shouldn't have brought up this point at all. But I'm trying to clarify the way the procedures SQUARES and FOREST-SQUARES work together. There are always a bunch of different ways of thinking about a program, and this is one of them.
The two procedures both deal with deep lists, i.e., lists of lists. In fact, because of the line REPORT (FOREST-SQUARES (TREE)) you can see that the two procedures deal with the same lists; the input to FOREST is passed along as input to FOREST-SQUARES.
But the two procedures treat their input as instances of two different abstract data types. SQUARES treats it as one tree, which is a two-dimensional structure that has to be traversed in two ways. FOREST-SQUARES treats it as a forest, i.e., a sequence of trees, a plain old list like (a b c d) except that each item is a tree instead of a character string. And the trees inside the forest are taken as black boxes, the same as you can think of the parking lane of a street as a sequence of cars without thinking about the various parts of a car or how they connect together.
And therefore FOREST-SQUARES is a plain sequential recursion. Consider this procedure that takes as input a sequence (a list) of numbers:
You should be able to understand that straightforwardly. Now compare that with FOREST-SQUARES. The only difference is what function of ITEM 1 OF SEQUENCE it computes. So, just as SEQUENCE-SQUARES can be replaced with a call to MAP, so can FOREST-SQUARES be replaced with a call to MAP.
Nah, teachers never make mistakes. ;~P
My apologies: I shouldn't have interfered.