# Intro to Recursion **URL:** \ **Category:** Tutorials (Here's how to...)\ **Created:** [January 25, 2026, 7:57pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304 "2026-01-25T19:57:28Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![bh](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/bh/32/31580_2.png) [@bh](https://forum.snap.berkeley.edu/u/bh)\ **Post date:** [January 25, 2026, 7:57pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/1 "2026-01-25T19:57:28Z")
We’ll start with pig Latin. To translate a word to pig Latin, you move its initial consonants to the end of the word, so that it starts with a vowel, and then append “ay”. So, “snap” in pig Latin is “apsnay”. ![untitled script pic (8)](https://cdn.forum.snap.berkeley.edu/original/3X/3/a/3ae75c001808d998af7356776e0242e42f0604f3.png) ![untitled script pic (7)](https://cdn.forum.snap.berkeley.edu/original/3X/5/e/5e902e3227aa4fb89a1ba5219894ed1f5ee17a50.png) ![untitled script pic (10)](https://cdn.forum.snap.berkeley.edu/original/3X/d/5/d57409dc88e7009fb2fac2db2afb2d5ec6a53be0.png) (This is a simplified version of the translation algorithm you learned as a kid. For one thing, _sometimes_ you have to consider Y to be a vowel, because otherwise a word such as “sky” doesn’t have any vowels. But we’ll ignore that to keep the program simple.) You don’t have any problem with one function calling _another_ function, such as PIG LATIN calling VOWEL?, right? The first function waits while the second function does its work, and then the first function carries on, using the value returned by the second one. You can imagine that inside the computer there are lots of little people, each of whom specializes in carrying out one procedure, so there’s a little person named Peter who knows how to do PIG LATIN, and one named Violet who knows how to do VOWEL?. Peter asks Violet whether the first letter of the word is a vowel, Violet answers True or False, and then Peter can give that answer to Isobel, who knows how to do IF. Well, recursion is exactly the same idea, but one little person asks **another** little person who specializes in _the same procedure_ to solve a subproblem. So, to write PIG LATIN you have to realize that the translation of “snap” into pig Latin is the same as the translation of “naps” – the word with just the first letter moved to the end of the word. And then, the translation of “naps” is the same as the translation of “apsn”. But “apsn” starts with a vowel, so we can just append “ay” to get “apsnay”. So, you ask Peter for the pig Latin for “snap”. Peter asks Pamela for the pig Latin for “naps”. Pamela asks Pavel for the pig Latin for “apsn”. And Pavel takes the first branch of the IF, because “apsn” starts with a vowel. * * * What gives people trouble about recursion is that they try to understand the recursive call as meaning “go back to the top of the procedure,” like this: ![untitled script pic (11)](https://cdn.forum.snap.berkeley.edu/original/3X/d/0/d0f1b0de8c42c12dc6f3b51414fe2fc4e87f3fab.png) This iterative version works, too, but only because PIG LATIN uses a particularly simple version of recursion, called “tail recursion,” in which the recursive call is the very last thing the procedure has to do. When students have trouble understanding recursion, it’s almost always because they are mentally translating the recursive version into the iterative version, and that stops working when you encounter non-tail recursion. Instead you have to think about little people, and understand the recursive call as two separate little people, Peter and Pamela (or Pamela and Pavel), independently running the same code. * * * Okay, on to non-tail recursion. People often find it easier to start with an imperative recursion rather than a functional one, so we’ll start by drawing a tree like this: ![Stage](https://cdn.forum.snap.berkeley.edu/original/3X/6/f/6f7c8996fdf2c55363cc3540cc11f12543549ae4.png) That’s a level-four tree, i.e., it has branches on branches on branches on the trunk of the tree. We’re going to work up to that in stages, so first we draw a level-one tree, which is just the trunk. But (planning ahead) we want to leave the turtle in the same place it started: ![untitled script pic (12)](https://cdn.forum.snap.berkeley.edu/original/3X/2/8/280c7f6ff5d15ab94066f8acac15c609aea00b40.png) ![untitled script pic (13)](https://cdn.forum.snap.berkeley.edu/original/3X/f/3/f3a892de9f2f8e6ebbbbe708fb23d6ed2169532d.png) ![Stage (1)](https://cdn.forum.snap.berkeley.edu/original/3X/e/e/eebdb7a34c76d16730cd043b7e639f8dfadf7eec.png) * * * Okay, on to a level-two tree. We could write it this way: ![untitled script pic (14)](https://cdn.forum.snap.berkeley.edu/original/3X/9/3/931a24b71c4b955f2bc7fbf2334355a86eccc080.png) ![untitled script pic (15)](https://cdn.forum.snap.berkeley.edu/original/3X/7/c/7c5e9641120a3580d3d7c3603b4b1fc4b05962a5.png) ![Stage (2)](https://cdn.forum.snap.berkeley.edu/original/3X/e/3/e36a97477056357b1386239d2cf1afa2122f9d2e.png) Note in passing that it’s now clear why we have to move back after moving forward: After drawing the left branch, we need the turtle to be in the correct position to draw the right branch. * * * But for levels higher than two, coding each branch with MOVE blocks would be too horrible to contemplate. So, notice that in the level-three tree, the left branch is a level-two tree: ![Stage (3)](https://cdn.forum.snap.berkeley.edu/original/3X/0/d/0da97cd33e8dee483331d03928611ef1c2f28a15.png) So we can code the level-three tree in a way that takes advantage of that understanding: ![untitled script pic (16)](https://cdn.forum.snap.berkeley.edu/original/3X/0/3/03d06bc508197a7eb13befe91839f8e0e0f45db9.png) (I’m going to stop showing the toplevel script; you get the idea of those. Also, a pedagogic side note: Arguably the TREE procedures belong more in the Motion category than in the Pen category, but putting them in Pen makes what will become the recursive calls stand out visually in the script.) Note that when we hire Trevor to draw a TREE3 of size 100, he hires Tabatha and Tom to draw TREE2s of size 75. Each little person has his or her own idea of what SIZE is. Saying that another way, each little person has his or her own local variables. We can imagine that each TREE3 and TREE2 little person has a pocket labelled SIZE that has some number in it. * * * From here, we can straightforwardly code higher-level trees: ![untitled script pic (18)](https://cdn.forum.snap.berkeley.edu/original/3X/f/8/f8092a07ae39017ba4a410f5d42f70850b3cb9fb.png) ![untitled script pic (17)](https://cdn.forum.snap.berkeley.edu/original/3X/c/f/cfe3dacf3f65c9855181c45336e183a57756c3f2.png) These procedures aren’t recursive; each one calls a lower-level helper procedure. So you should have no trouble convincing yourself that they all work. There’s a lot of procedure calling going on, though; if you draw a TREE5, you need 16 little people who know how to draw a TREE1. Which reminds me: I’m going to rewrite TREE2 so that it looks like the others: ![untitled script pic (19)](https://cdn.forum.snap.berkeley.edu/original/3X/5/8/582502bb7714a6d958990977a6d52d8f77fab5ba.png) * * * So, in principle, we can make arbitrarily complicated trees by making blocks TREE6, TREE7, and so on. But it’d be too horrible to contemplate if we wanted to make a level-100 tree that way! Instead, we notice that all these procedures look almost the same; it’s just the two calls (left and right branches) to the next-lower-level TREE procedures that differ. So the big insight is that by _adding another input_ we can capture that difference and collapse them all into one block: ![untitled script pic (20)](https://cdn.forum.snap.berkeley.edu/original/3X/4/a/4a95f65717a51044ecc1ea36c614fa393612a529.png) Unfortunately, this procedure doesn’t work. It keeps trying to draw smaller and smaller left branches, so the turtle ends up spinning around at the top: ![Screenshot 2026-01-25 at 10.35.48 AM](https://cdn.forum.snap.berkeley.edu/original/3X/6/0/605ae5f5f4decb300ef38dc3a8ae612fabd5c7d7.png) This is a typical student bug in using recursion. The problem is that it isn’t quite true that all the numbered TREE procedures are the same. The first one is different from the others: ![untitled script pic (12)](https://cdn.forum.snap.berkeley.edu/original/3X/2/8/280c7f6ff5d15ab94066f8acac15c609aea00b40.png) TREE1 does its work all by itself, without calling a (nonexistent) TREE0 procedure. A level-one tree doesn’t have left and right branches; all it has is a trunk. This illustrates a general rule of recursion: there has to be a _ **base case** _ that the procedure knows how to handle without calling itself recursively. So the correct TREE procedure looks like this: ![untitled script pic (21)](https://cdn.forum.snap.berkeley.edu/original/3X/2/e/2ec0d8e0027b374fda437b96d2856fab0bbb68f7.png) Every recursive procedure needs a base case. In PIG LATIN, the base case is that the word starts with a vowel. Don’t forget that even though they’re all running the same code, each TREE person has his or her own SIZE pocket. So when we hire Tammy to draw a TREE8 of size 100, she hires Terry to draw a TREE7 of size 75, but Tammy’s SIZE pocket still has 100 in it. It doesn’t change to 75! This is why you can’t mentally translate the recursion into a loop like ![untitled script pic (22)](https://cdn.forum.snap.berkeley.edu/original/3X/b/4/b465b4695c15855a3b2e11dd16dab466037063d4.png) the way you could in the case of PIG LATIN. This is a general rule: Any time you find yourself thinking the words “go back” in computer programming, you’re in trouble. You have to think little people instead. * * * Almost done. Recursive reporters (functions) are just like recursive commands, except that the recursive call(s) are embedded in a larger expression. So, here’s a procedure to list the moves to solve the Towers of Hanoi problem: ![untitled script pic (25)](https://cdn.forum.snap.berkeley.edu/original/3X/9/2/928ff61e86ceedb7c489491507d127164b391c5c.png) ![untitled script pic (26)](https://cdn.forum.snap.berkeley.edu/optimized/3X/f/3/f3402af300a40cb057fbe68663ca0cbe9ecc5386_2_517x51.png) (Again, I’ve chosen to put the block in an unnatural category so that the recursive calls stand out.) The base case is a one-disk tower; you just move the one disk where you want it. With more than one disk, you first move the top n-1 disks out of the way, then you can move disk n, and then you move the other n-1 disks on top of it. * * * If you want all this spelled out more slowly, you can read my Logo books: > **[Computer Science Logo Style vol 1 ch 7: Introduction to Recursion](https://people.eecs.berkeley.edu/~bh/v1ch7/recur1.html)** or my Scheme book: > **[Simply Scheme: Introducing Computer Science, Part 11: Recursion](https://people.eecs.berkeley.edu/~bh/ssch11/part4.html)** (In both cases, the link points to the first of several consecutive chapters about recursion.) ---
**Author:** ![cymplecy](https://forum.snap.berkeley.edu/letter_avatar_proxy/v4/letter/c/47e85d/32.png) [@cymplecy](https://forum.snap.berkeley.edu/u/cymplecy)\ **Post date:** [January 26, 2026, 1:30pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/2 "2026-01-26T13:30:38Z")
Thanks for all this 🙂 I got the first example and I caI usually can do this sort of simple stuff myself and have done so in the past 🙂 I followed the tree story and all good but at the end, I thought - it isn’t much different than the first pig latin code I’ll go off and have a read of your books and then come back 🙂 ---
**Author:** ![cymplecy](https://forum.snap.berkeley.edu/letter_avatar_proxy/v4/letter/c/47e85d/32.png) [@cymplecy](https://forum.snap.berkeley.edu/u/cymplecy)\ **Post date:** [January 26, 2026, 2:07pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/3 "2026-01-26T14:07:05Z")
#LOL Read a bit - decided to try writing a reverse (from memory of what I’d just read) - crashed Snap! 🙂 Have I mentioned that I can’t do recursion 🙂 Got it on 3rd attempt ![reverse recursion script pic](https://cdn.forum.snap.berkeley.edu/original/3X/2/5/25df481636a6c30056eef7a942006f4ea2fbca95.png) Note: I arrived early at an airport (by 5 hours) so I have got some time to devote to my studies today 🙂 ---
**Author:** ![jens](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/jens/32/39797_2.png) [@jens](https://forum.snap.berkeley.edu/u/jens)\ **Post date:** [January 26, 2026, 5:48pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/4 "2026-01-26T17:48:35Z")
this is super nice, Brian, thank you!! ---
**Author:** ![bh](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/bh/32/31580_2.png) [@bh](https://forum.snap.berkeley.edu/u/bh)\ **Post date:** [January 26, 2026, 6:52pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/5 "2026-01-26T18:52:03Z")
> I followed the tree story and all good but at the end, I thought - it isn’t much different than the first pig latin code The difference is that there are two recursive calls, not just one. And after the recursive calls, there’s still work to be done (moving back down the trunk). The usual way to misunderstand recursion is to think that there’s just one variable named LEVEL and one named SIZE, so after TREE 5 100 does the first recursive call TREE 4 75, its LEVEL now contains 4 and its SIZE now contains 75, so the second recursive call does TREE 3 56.25 (3/4 of 75), and the MOVE at the end moves back 56.25 steps. If you understand PIG LATIN the same way you understand TREE, that’s great! Good job on REVERSE. :~) ---
**Author:** ![owlsss](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/owlsss/32/45047_2.png) [@owlsss](https://forum.snap.berkeley.edu/u/owlsss)\ **Post date:** [January 27, 2026, 3:36pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/6 "2026-01-27T15:36:35Z")
heheh ![image](https://cdn.forum.snap.berkeley.edu/original/3X/d/4/d408b4a0d44dab410fbd9dfcb82b375e0cac5da0.png) ---
**Author:** ![sathvikrias](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/sathvikrias/32/46248_2.png) [@sathvikrias](https://forum.snap.berkeley.edu/u/sathvikrias)\ **Post date:** [January 27, 2026, 4:47pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/7 "2026-01-27T16:47:31Z")
@loucheman made something similar: > [@Merge 2D lists](https://forum.snap.berkeley.edu/t/merge-2d-lists/21299/34): > > > [@Merge 2D lists](https://forum.snap.berkeley.edu/t/merge-2d-lists/21299/33): > > > > ![untitled script pic (8)](https://cdn.forum.snap.berkeley.edu/original/3X/3/a/3ae75c001808d998af7356776e0242e42f0604f3.png) > > This remind me something: > ![untitled script pic (9)](https://cdn.forum.snap.berkeley.edu/optimized/3X/e/1/e1ddd5785eccdde23bf5fa2c8b44a1fe1fe18844_2_690x53.png) > (with a little modification) > @ego-lay_atman-bay ---
**Author:** ![owlsss](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/owlsss/32/45047_2.png) [@owlsss](https://forum.snap.berkeley.edu/u/owlsss)\ **Post date:** [January 27, 2026, 7:04pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/8 "2026-01-27T19:04:05Z")
> [@sathvikrias](#): > > @loucheman made something similar: I did not read that thread. ---
**Author:** ![snapenilk](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/snapenilk/32/1947_2.png) [@snapenilk](https://forum.snap.berkeley.edu/u/snapenilk)\ **Post date:** [January 28, 2026, 7:03pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/9 "2026-01-28T19:03:58Z")
I found a detailed tutorial about recursion [here](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304). ---
**Author:** ![coder\_07](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/coder_07/32/27507_2.png) [@coder\_07](https://forum.snap.berkeley.edu/u/coder_07)\ **Post date:** [January 28, 2026, 8:18pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/10 "2026-01-28T20:18:11Z")
> [@snapenilk](#): > > here thats just a link to this topic though?? edit: oh i get it ---
**Author:** ![specialred](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/specialred/32/38878_2.png) [@specialred](https://forum.snap.berkeley.edu/u/specialred)\ **Post date:** [January 28, 2026, 8:26pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/11 "2026-01-28T20:26:33Z")
lol! ---
**Author:** ![cymplecy](https://forum.snap.berkeley.edu/letter_avatar_proxy/v4/letter/c/47e85d/32.png) [@cymplecy](https://forum.snap.berkeley.edu/u/cymplecy)\ **Post date:** [January 28, 2026, 9:12pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/12 "2026-01-28T21:12:36Z")
Well played 🙂 ---
**Author:** ![sathvikrias](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/sathvikrias/32/46248_2.png) [@sathvikrias](https://forum.snap.berkeley.edu/u/sathvikrias)\ **Post date:** [January 28, 2026, 9:41pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/13 "2026-01-28T21:41:14Z")
it’s literally the same topic, why ---
**Author:** ![snapenilk](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/snapenilk/32/1947_2.png) [@snapenilk](https://forum.snap.berkeley.edu/u/snapenilk)\ **Post date:** [January 28, 2026, 9:59pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/14 "2026-01-28T21:59:30Z")
[Google recursion](https://www.google.com/search?num=10&client=ms-android-tmus-us-rvc3&hs=3DaU&sca_esv=c2f1926528fd7bde&sxsrf=ANbL-n5DIuM9dQwvNls7hlT9IpD6WrvQxw:1769637587401&q=recursion&spell=1&sa=X&ved=2ahUKEwjlyJzena-SAxWwKlkFHTSdLiEQBSgAegQIDhAB&biw=411&bih=753&dpr=2.63&aic=0) ---
**Author:** ![sathvikrias](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/sathvikrias/32/46248_2.png) [@sathvikrias](https://forum.snap.berkeley.edu/u/sathvikrias)\ **Post date:** [January 28, 2026, 11:29pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/15 "2026-01-28T23:29:18Z")
I already had known what recursion was. ---
**Author:** ![specialred](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/specialred/32/38878_2.png) [@specialred](https://forum.snap.berkeley.edu/u/specialred)\ **Post date:** [January 28, 2026, 11:32pm UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/16 "2026-01-28T23:32:40Z")
it’s a joke on recursion ---
**Author:** ![sathvikrias](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/sathvikrias/32/46248_2.png) [@sathvikrias](https://forum.snap.berkeley.edu/u/sathvikrias)\ **Post date:** [January 29, 2026, 12:31am UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/17 "2026-01-29T00:31:15Z")
it’s a hyperlink. ---
**Author:** ![d016](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/d016/32/42496_2.png) [@d016](https://forum.snap.berkeley.edu/u/d016)\ **Post date:** [January 29, 2026, 12:33am UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/18 "2026-01-29T00:33:33Z")
\> recursion is about calling the same thing that calls the recursive \> someone puts a link (calling) which is the same topic (calling the same function) that’s the joke ![image](https://cdn.forum.snap.berkeley.edu/original/3X/b/1/b1fdd6cb6b70c1564df4323b860872253d87b82c.png) ---
**Author:** ![sathvikrias](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/sathvikrias/32/46248_2.png) [@sathvikrias](https://forum.snap.berkeley.edu/u/sathvikrias)\ **Post date:** [January 29, 2026, 12:34am UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/19 "2026-01-29T00:34:21Z")
I’m really not understanding how the post isn’t just spam, so I think i’ll disengage w the conversation. ---
**Author:** ![mark4sisb](https://forum.snap.berkeley.edu/user_avatar/forum.snap.berkeley.edu/mark4sisb/32/32632_2.png) [@mark4sisb](https://forum.snap.berkeley.edu/u/mark4sisb)\ **Post date:** [January 29, 2026, 2:45am UTC](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304/20 "2026-01-29T02:45:10Z")
> [@sathvikrias](#): > > I’m really not understanding how the post isn’t just spam, so I think i’ll disengage w the conversation. Recursion is a function that calls itself. The tutorial on recursion now links to the tutorial on recursion; effectively calling itself. When you Google “recursion”, it says “Did you mean: _recursion_”, which is the same word. If you click on it, you get taken to the same page, which once again says “Did you mean: _recursion_”. It is a joke on the idea of recursion. [Next page](https://forum.snap.berkeley.edu/t/intro-to-recursion/21304.md?page=2)