# Explainable recursion

I never really understood how exactly a tree is recursively made step-by-step, so I made this project to follow the process and see what exactly happens at each level from 6 to 0 (in slow motion).

You can turn the explanations off (by setting the 'explain' variable watcher/slider to 0) and on again, at any moment. Independently of this you can also slow down (and speed up, again) everything by setting the 'speed' slider to either 1 or 2.

great explanation! can you make an option where you click to go to the next step?

If it was an iterative script, I could do it; but since it is a recursive one, I don't think it is possible.

(Unless I am not understanding the whole recursion thing correctly.)

I wonder what others think.

Is it possible?

At the places with the say [] and for () secs blocks, you can add wait until <mouse down?>.

Oh, I thought sathvikrias wanted it to draw the next branch on click, so it wouldn't be necessary to wait for the current tree branch to be drawn step-by-step.

When you say (for example) "level 4 do this" "(still) level 4 do that" ... "level 3 do this" ... "(still) level 4 do that" I find that last "still" confusing. It should be "(back to) level 4" or some such thing.

But I have a deeper question about this whole approach. I guess some people do learn to understand recursion by tracing the code, but I find with students that that doesn't help them write their own recursive programs to do something different. For that, you have to learn to take on faith that the recursive call will do what it claims to do, and see how that fits into the current level. So my idea of a pedagogic tree project would be this:

P.S. In case it isn't clear (people tell me my emails are too terse), I don't mean to say your approach is useless. I'm trying to start a conversation about how to teach recursion, a topic dear to my heart. Students definitely ask for what you're presenting! Nobody asks for my version, I think because they don't know they need it until they get it.

You are right. Recursion has always been a great mystery to me and I wouldn't be able to write my own recursive program.

I could only agree that your version teaches the recursive logic better than mine does, but yeah it wasn't the project's purpose to expose the logic in the first place (since I still don't understand it enough to be able to teach it).

I was just curious what exactly happens at each level. Especially I wanted to see what happens at the level 1.

Try reading chapters 7-9 and 11 of CSLS vol 1 and see if that helps!

I think this is about how to represent/imagine/visualize recursion, right? Well how I imagine the tree-drawing program is that the tree is made out of smaller trees. So you have a function that draws a tree: it draws the trunk and then draws two smaller trees slightly to the left and right. To draw the smaller tree, you use the same function you use to draw a tree. And a Sierpinski triangle is made out of smaller Sierpinski triangles. I wrote a program to construct one recursively once -- it worked by taking a triangle, got the midpoint of each triangle edge, and made three Sierpinski triangles using those three midpoints and the triangle's vertices. So in my mind a recursive function is basically iteration done by calling itself, I guess. Is this relevant to this topic?

Yes, this is the key idea to understand in recursive procedures. You do seem to understand that very well.

Definitely relevant, but "iteration" doesn't describe it correctly. Think about trying to draw the fractal tree with a loop. While the program is drawing, let's say, a level 3 trunk (where the whole tree is level 6), it has to remember somehow which level 3 trunk it is (there are eight of them), i.e., what remains to be done after drawing this level 3 subtree. That information isn't represented explicitly in the code; it's remembered by virtue of the fact that while the level 3 tree is being drawn there's a level 4 invocation, a level 5 invocation, and the (toplevel) level 6 invocation, each of which remembers whether it's in the middle of its left branch or its right branch. Also, each of those invocations remembers how long a trunk it's supposed to draw, and therefore what the length input should be in its two recursive calls. And remember that there could be any number of branches, and they don't have to be symmetrical! Think about drawing this tree iteratively:

(made with my interactive tree project). Each recursive call has to know what color it's drawing, how thick, how far up the trunk, etc. You could do it iteratively by storing all that information in an explicit data structure, but I don't think that's what you were envisioning when you said "iteration." Reading your mind, you were thinking the recursive call means "go back to the top of this script." I always tell my students to listen for themselves thinking "go back" and immediately stop that thought before even finishing the sentence!

A recursive call that's the last thing that happens in a procedure is equivalent to an iteration, because if the procedure has no more work to do, it doesn't have to remember anything. But note that in a recursive reporter, it's not enough that the recursive call is in the REPORT instruction; it has to be the one that reports directly to the REPORT block. So,

is not iterative, because after the recursive call returns, the current call has to multiply the value it reported by N. But this:

is iterative, because the multiplication happens before the recursive call.

I've read chapters 7 to 9 - reading the explanations definitively helps, but I won't say that I 100% understand recursion now. Better than before for sure.

I agree. Will change it. On the other hand, I wonder would it be possible to draw branches of the same level simultaneously? For example, using clones of the sprite? So that the drawing will appear in the following order:

1. Trunk (i.e. 'Level 6')
2. Simultaneously the 2 (of the 'Level 5') branches
3. Simultaneously the 4 (of the 'Level 4') ones
4. Simultaneously the 8 (of the 'Level 3') ones
5. Simultaneously the 16 (of the 'Level 2') ones
6. Simultaneously the 32 (of the 'Level 1') ones

Of course it's possible, but I think it's steering you away from the original goal of explaining recursion. This instead makes it a lesson in multithreading.

I wonder if you can write a procedure that goes just 'down' (until the word is five letters long), not 'downup'?

Sure! Just leave out one of the PRINTs. The one at the beginning is doing the "down" part and the one at the end is doing the "up" part.

Hm, but in chapter 7 of your "CS Logo style" book it says:

Maybe try it in Snap! (using say instead of print) and see what happens?

Oh, yeah, that's because there's only one copy of the one-letter center. But you can work it out! It's not that hard.

Or try it in Berkeley Logo.