How to understand the base case of a recursion

Tutorials (Here's how to...)
, ,
22

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?

23

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!)

24

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.

25

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.

highlighting the all but the first of block
highlighting the all but the first of block1280×762 308 KB

26

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."

27

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.

28

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.

29

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:

untitled script pic
untitled script pic1288×500 93.2 KB

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

30

My apologies: I shouldn't have interfered.

31

No problem.

32

I am grateful that you joined the discussion so I'm not the only one here risking 'losing face' by asking 'stupid questions', exposing my own (wrong) assumptions or 'hallucinations' that we humans tend to frown upon when AI bots do it, but we are also prone to doing it.

It seems that in our world's mostly competitive cultures, children only are allowed to be 'stupid', not knowing something that others presumably know; and grownups are prohibited to do any of these. (That's why I prefer to have 11-years old me as my profile picture, it allows me to do all the above.)

33

This explanation is much more accessible to my non-mathematician mind. I like it.

I like it how you made a comparison between that more straightforward script and the one you are trying to explain to me. Now it is even more accessible.

34

Haha, I was actually trying to provide answers :grinning:

But I deeply agree with your point that one should allow oneself, and others, to ask 'stupid questions'. That's what learning is all about, really.

35

This competition about which of you is asking stupider questions isn't really helping advance anyone's understanding. :~P And it's embarrassing me. When I said "teachers never make mistakes" it was a joke! I make mistakes all the time, including elementary ("stupid") mistakes.

Really this whole discussion of tree traversal has gotten us away from the original point. I picked that example to illustrate that reaching the base case of a recursion doesn't mean the task is finished. In retrospect I should have picked two simpler examples:

  1. Factorial. This is the paradigmatic "when you reach the base case the task is complete" kind of recursion -- except that it's not true, because the work is done "on the way out" of the recursion, so reaching the base case means the task is just beginning!
    untitled script pic
    The key point is that in the last instruction, Snap! can't do the multiplication until after it gets a reported value from the recursive call. So if you ask for (! 3) the sequence of events is
Try to compute (3 x (! 2)) but need (! 2).
  Recursive call (! 2):
  Try to compute (2 x (! 1)) but need (! 1).
  Recursive call (! 1):
  Try to compute (1 x (! 0)) but need (! 0).
    Recursive call (! 0):
**    Base case, report 1.         **
**    Compute and report (1 x 1).  **
**  Compute and report (2 x 1).    **
**Compute and report (3 x 2).      **

All the work is done in those last four lines, which start when the base case is recognized.

  1. Pascal's triangle. This case makes the point about tree recursion without getting sucked into actual list structures:
    untitled script pic (1)
    untitled script pic (1)984×480 86 KB

    This says that the number we want is the sum of the two numbers above it, except that the numbers at the edges are 1. That requires two recursive calls before the + can happen. When the first recursive call reaches its base case, only about half the work has been done.

(Yes, this could be made more efficient, but we're not going to go down that rabbit hole right now.)

But we're still looking at my code instead of yours! :~(

36

I experimented with asking ChatGPT 4 Brian's first example of buggy recursion:

Here's the result: https://chat.openai.com/share/e13da47c-504e-413c-a6a6-5d08ac992efb

37

Very impressive :slight_smile:

38

Not bad, although listing the existence of a primitive version as a "reason it doesn't work" is a little harsh. But it gets points for recognizing this as something you'd do for pedagogic purposes.

It's wrong about IS _ EMPTY? Its knowledge of Snap! is a little dated. :~)

39

Did I say I liked your 'trick'? I do.

Today I've read a post, written by a math teacher who is also interested in research on what works in teaching and why it works, that has reminded
me of the 'trick'.

And it occurred to me the 'trick' must be an example of what is called a 'generalization' that he is writing about below in his:

Pershan's "Pyramid" of Teaching Greatness

As I understand his post, trying to rephrase it bellow, he says:

I think a lot about writing, and
I think a lot about teaching.

Here's a diagram:
Pershan_teaching_pyramid_of_greatness_01

Articulating the Pershan's diagram in my words, a teacher starts with some examples,

  • starting from the bottom left Specifics,

  • then guiding students up in the air to some generalization,

  • and finally letting each student apply (his/her/their own) understanding of the abstraction to another Specifics bottom right in the diagram,

  • because it is just not enough for a student to either just hear or (even) articulate an abstraction to prove its understanding.

  • to really prove its understanding, each student needs to apply it to other specific cases which were not contained in 'the training dataset' (1)

(1) If I am allowed to use the words that are used in the Large language model - Wikipedia parlance.

What do you think?

P. S.
I quote Pershan, "Besides, it’s not even a pyramid! It’s a line with a bump. Come on, people." referring to Freytag Pyramid that inspired him,
"You’ve probably seen Freytag’s Pyramid a few dozen times - it’s overused, abused, and has led to people making some very narrow and reductive claims about what constitutes a good story. Lincoln Michel, for example, has written about the need to think more broadly about story structure, and in my own less-prominent experience he’s correct."

P. P. S.
He also says: "I should admit at this point that I stole this specifics/generalization/specifics thing from a lovely piece that I’ve written about before by researchers Alexander Renkl and Alexander Eitel.

They have a busier version of what I’m talking about that has really influenced my teaching."
the_2017_diagram_by_Renkl

P. P. P. S.
He additionally says:
"And here’s a weird thought: if you tilt your head enough, 'show don’t tell,' the popular creative writing admonition, is pretty similar to the teaching mantra 'never say anything a kid can say.' OK, fine, they’re not exactly parallel! But they’re both trying to warn you, as someone trying to engage others, that simply articulating your views isn’t enough."

40

So it helped you! Thanks for the compliment.

And, indirectly, it may have promoted your interest in Pershan’s article on teaching. Good for you!

41

I have a small question about a problem I've been having considering recursion, and this forum post feels like the right place.
I have a reporter function, shown in the image, for calculating the lowest significant digit of a number (its for a modified calculator). The reporter itself has a parameter called "level" that's supposed to always start at 1 when you start it, then go up by one each time it recurses.
This is completely cosmetic, and wont be seen by anyone else unless they want to see the code, but how would I make it so that the "level" parameter doesn't show up on the main coding space. More succinctly, how do I send data between recursion levels without using an extra parameter?