<p>I like to use something that a student can connect with and something that they have to deal with regularly. You could choose any recursive everyday activity, but I like to choose revising an essay.</p>

<p>Let's say you've already written your essay, and now you want to go back and perfect it. First you read the essay again, then you get feedback from others, then you make the changes, and then you revise the essay unless you consider your essay complete. In pseudocode:</p>

<pre><code>function revise(essay) {
  read(essay);
  get_feedback_on(essay);
  apply_changes_to(essay);
  revise(essay) unless essay.complete?;
}
</code></pre>

<p>After the students understand the basics of what recursion is by following the simple example above or one like it, I'd move on to more sophisticated examples of recursion like a simple sort. Take merge sort for example (this assumes arrays have been taught):</p>

<pre><code>function sort(array) {
  a = array.first_half;
  b = array.second_half;
  sort(a);
  sort(b);
  merge(a,b);
}

function merge(a,b) {
  final = [];
  a_counter = 0;
  b_counter = 0;
  while (final.length &lt; a.length*2) {
    if a[a_counter] &lt; b[b_counter] {
      final.push(a.shift);
      a_counter++;
    } else if (b[b_counter] &lt; a[a_counter]) {
      final.push(b.shift);
      b_counter++;
    }
  }
  return final;
}
</code></pre>

CC BY-SA 3.0
2017-05-23T21:08:31.730Z
You've shown tail-recursion on a problem of the same size at each function invocation, and have thus merely reformulated a `do {...} until` block. This doesn't demonstrate the general power of recursion. To keep with your example, I prefer a formulation like this:

`function revise(essay) {
    if essay.scale > sentence {
        foreach s in essay.subsections {
            revise(s);
        }
    }
    do {
        read(essay);
        get_feedback_on(essay);
        apply_changes_to(essay);
    } until essay.complete?
}`
Andrew Sundstrom
CC BY-SA 3.0
2018-01-11T02:17:22.980Z
The first one is just a loop...
Criticize SE actions means ban
CC BY-SA 3.0
2017-05-23T15:58:30.917Z
2017-05-23T21:53:40.430Z
2017-05-23T21:53:40.430Z
thesecretmaster
<h3>Recursion as a loop</h3>
<p>I'd present recursion as a form of a loop rather than being separate thing.  Then, I'd show the students how to covert between flat form and recursive form, and discuss the pro's/con's of using both in implementation.</p>
<h3>Flat-vs.-recursive formats rather than examples of recursion</h3>
<p>Since any loop can be written in recursive format, there's basically infinitely many examples that could be presented.  But, some seem to make more sense to people in recursive form than others.  Why?</p>
<p>This could be a fruitful avenue for class discussion.  For example, another answer here gave the example of fractals - why should fractals be seen as more recursive than, say, counting, when both loops can be written in flat form or recursive form just as easily?  Then what does this imply - should we just always use one form over the other, or do they each have their place?</p>
<p>I love discussions like this, and I think that they could make the class fun!</p>
<h3>Ideas for coursework (homework/projects):</h3>
<ol>
<li><p><em>[intro-level]</em>  Students are given a large number of loops in flat form, then must rewrite them in recursive form.</p>
</li>
<li><p><em>[intro-level]</em>  Students are given a large number of loops in recursive form, then must rewrite them in flat form.</p>
</li>
<li><p><em>[college-level]</em>  Short-answer questions about which form they should use in real-life coding scenarios.  For example, in some situations flat form's much preferable to avoid stack overflows and implement tail-call optimization when not supported by the underlying platform.</p>
</li>
<li><p><em>[college/grad-level]</em>  Write an interpreter or meta-programming function that converts between flat and recursive forms.</p>
</li>
</ol>

CC BY-SA 4.0
2021-09-03T10:31:28.797Z
_"Then, I'd show the students how to covert between flat form and recursive form, and discuss the pro's/con's of using both in implementation."_ Due to the finite stack, if you **can** convert between a loop or recursion, the loop is objectively superior. Recursion is reserved for those cases where loops simply don't cut it (or become insanely complex)
Flater
CC BY-SA 3.0
2017-05-23T16:41:28.140Z
2017-05-23T16:58:27.177Z
2020-06-18T08:36:57.023Z
Nat
<p>The <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi" rel="noreferrer">Tower of Hanoi</a> was one of the first ways that I encountered recursion.</p>

<p><a href="https://i.sstatic.net/dEbk3.png" rel="noreferrer"><img src="https://i.sstatic.net/dEbk3.png" alt="Tower of Hanoi, cc by-sa Bin im Garten"></a></p>

<p>"The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:</p>

<ol>
<li>Only one disk can be moved at a time.</li>
<li>Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.</li>
<li>No disk may be placed on top of a smaller disk." (from Wikipedia)</li>
</ol>

<p>To solve the n disk tower problem:</p>

<ol>
<li>Solve the n-1 disk tower problem </li>
<li>Move the nth disk </li>
<li>Solve the n-1 disk tower problem again.</li>
</ol>

<p>Solving the 1 disk problem is trivial. </p>

<p>I can imagine coding this as a nice on-screen or physical computing challenge.</p>

CC BY-SA 4.0
2022-03-02T16:50:46.477Z
Yes! I remember seeing this on an educational TV programme in Germany, and I found this so elegant. I was then very disappointed when I realised that the BASIC dialect that I used did not support recursion (directly). Well, it was a reason to learn Pascal later :)
Carsten S
CC BY-SA 4.0
2022-06-23T22:43:31.633Z
I find this a really good example because — unlike many of the other examples — this one _can't_ be seen as a fancy way of writing an iterative algorithm.
gidds
CC BY-SA 3.0
2017-05-24T06:00:17.223Z
2017-05-24T06:00:17.223Z
Miles
<p>Can't claim it's my own idea but I can embellish it a little...</p>

<p>Imagine you are entering a cinema. You sit down in a row but realise you had to sit in row 20. Being a lazy computer scientist in an already full theatre of other computer scientists (they're all there watching War Games again) you decide to recursively determine your row. </p>

<p>You ask the person in front. Trouble is they didn't check either. So again being lazy they ask the person in front of them. This continues until the bottom row is reached. This person knows they are in row 1 (they are there with a computer scientist friend but they aren't a computer scientist so they start counting at 1 not 0).</p>

<p>This is passed back to the person who asked, who being a computer scientist can add 1 to the number this person told them. This carries on until the original person asking finds out that the row in front of them is 31 and that must mean they are in 32.</p>

<p>He doesn't move though as he converts the value to hex to convince himself that it is row 20. He likes efficiency!</p>

<p><em>Cheo, C. (2015). 40 Key Computer Science Concepts Explained In Layman’s Terms. [Online] Available at: <a href="http://carlcheo.com/compsci" rel="noreferrer">http://carlcheo.com/compsci</a></em> </p>

CC BY-SA 3.0
2017-06-18T18:32:53.993Z
Nice, with a cute ending :)
Ben I.
CC BY-SA 4.0
2018-07-28T23:36:04.727Z
Glad it's a computer scientist and not an anthropologist. Otherwise the hex conversion would be cause for using a counter-curse.
Gypsy Spellweaver
CC BY-SA 3.0
2017-06-18T18:05:35.370Z
2017-06-18T18:30:11.057Z
2017-06-18T18:30:11.057Z
Stuart Davison
<p>The image that I kept in my head when I was learning recursion was from Dr. Seuss: 
<a href="https://i.sstatic.net/NFZVv.jpg" rel="noreferrer"><img src="https://i.sstatic.net/NFZVv.jpg" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-06-03T13:02:58.900Z
I like that this is imperfect as an analogy, gives scope for discussion.
Sean Houlihane
CC BY-SA 3.0
2017-06-18T18:08:06.257Z
@richard no. they don't need to. otherwise you get stackoverflow.
ItamarG3
CC BY-SA 3.0
2017-06-18T20:57:52.197Z
@ItamarGreen but as can be seen from the image, the stack is a cat stack. If every can in a hat had a cat in there hat, then the stack would not overflow, because it would be infinite. This could lead to a very tall stack of cats, but as each cat is getting smaller. it may be asymptotic. For example if each cat was half the size of the one bellow then the hight for an infinite number of cats would be 2×size_of_bottom_cat.
ctrl-alt-delor
CC BY-SA 3.0
2017-08-08T04:10:45.627Z
As a katz in a hat, I always enjoy cats in a hat.
manassehkatz-Moving 2 Codidact
CC BY-SA 3.0
2017-09-23T14:04:36.573Z
I read this to my intro class when we introduce recursion. It's not a perfect match, but works really well to intro the concept. Plus, high school kids love it when their teacher reads them a Dr. Seuss book.
Ryan Nutt
CC BY-SA 3.0
2017-05-26T15:24:07.887Z
Downvote with no comment? The OP asked for an _analogy_. IMO the Cat in the Hat's Little Cats are a perfect analogy.
G. Ann - SonarSource Team
CC BY-SA 3.0
2017-05-28T16:12:35.903Z
Do all cats in the hat, have a cat in their hat?
ctrl-alt-delor
CC BY-SA 4.0
2019-04-07T15:41:47.220Z
I just rediscovered this answer, and I wish I could upvoted it a second time. It's just so delightful!
Ben I.
CC BY-SA 4.0
2019-06-10T21:25:41.873Z
is there an end state to the cat in the hat?
pluke
CC BY-SA 4.0
2019-06-11T12:13:15.167Z
@pluke I don't have the book in front of me, but the interwebs tell me it's Little Cat Z.
G. Ann - SonarSource Team
CC BY-SA 3.0
2017-05-24T11:34:02.930Z
2017-05-24T11:34:02.930Z
G. Ann - SonarSource Team
<p>One of my favorite examples of recursion is evaluating an arithmetic expression.  The downside is that evaluation isn't particularly interesting, but the upside is significant: they've already done it in a programming course!  Usually, you'll very early on cover order of operations and expression evaluation in a programming course--but the algorithm we teach them is recursive "find the innermost expression, evaluate it, then move outwards".  Here's an example of it in use: <a href="http://courses.cs.washington.edu/courses/cse143/16au/lectures/power-of-recursion/lecture12-recursion.pdf" rel="noreferrer">http://courses.cs.washington.edu/courses/cse143/16au/lectures/power-of-recursion/lecture12-recursion.pdf</a></p>

CC BY-SA 3.0
2017-10-05T23:20:29.423Z
"find the innermost expression, evaluate it, then repeat"" is actually a *non-recursive* algorithm for expression evaluation.
Criticize SE actions means ban
CC BY-SA 3.0
2017-10-07T00:16:53.563Z
The "move outwards part" is usually implemented via recursion.
adamblan
CC BY-SA 3.0
2017-05-23T15:07:03.810Z
2017-05-23T15:07:03.810Z
adamblan
<p>I've used Carl Burch's analogy several times</p>

<blockquote>
  <p>Somebody is a Jew if she is Abraham's wife Sarah, or if his or her mother is a Jew. </p>
</blockquote>

<p><a href="https://www.cs.cmu.edu/~cburch/survey/recurse/index.html" rel="noreferrer">He has a nice set of pages at CMU</a></p>

CC BY-SA 3.0
2017-06-14T17:02:15.013Z
That's a really clear example. Nice!
Ben I.
CC BY-SA 3.0
2017-06-15T07:30:44.330Z
I'm Jewish and my daughter just had a bat mitzvah, but her mother is not Jewish. Many if not most Jews don't follow the custom given in this answer. It is a recent custom relative to Torah, which describes many non-Jewish women having Jewish children with a Jew. My daughter wants to be a software engineer and I think this example would make her feel badly. Not to expect political correctness, but I'd avoid this example because it misrepresents Judaism to non-Jews. Then again, the rule is absolutely recognizable to any Jew and anyone like my daughter can let it roll off. Thanks for sharing!
Bennett Brown
CC BY-SA 3.0
2017-06-15T19:42:57.890Z
I believe Dr Burch says somewhere, he overheard it at a dinner party and it's not a canonical method of determining whether someone is Jewish. Just a neat analogy for recursion.
JPearse
CC BY-SA 3.0
2017-08-08T04:16:02.803Z
In addition to patrilineal descent (many Reform Jews today, not accepted by Orthodox - and also debatable as to patrilineal vs. matrilineal before the Torah was given to the Jewish people, but I digress) and conversions (which obviously break the algorithm), this leaves open the question of whether Abraham himself was Jewish. As with so many other things in computer science, the edge cases will get you every time!
manassehkatz-Moving 2 Codidact
CC BY-SA 3.0
2018-01-13T07:15:54.467Z
@BennettBrown, I think it's a good analogy, and can be accompanied by a statement that this isn't a *real* definition of Judaism, just a useful analogy for demonstrating recursion.
Wildcard
CC BY-SA 4.0
2018-05-20T02:10:23.340Z
It *is* cute.  But aside from the fact that it's not really correct, as already noted, it really describes a recursive data structure.  Now recursive programs are naturally used to process recursive data structures.  But in my experience, recursive definitions of recursive data structures are even more magical and mysterious to students than recursive functions are.  Of course, once you get the idea you realize how natural and powerful this all becomes.  But for undergraduates, from what I've seen, it's extremely sophisticated.
Carl Offner
CC BY-SA 3.0
2017-06-14T16:58:11.397Z
2017-06-14T16:58:11.397Z
JPearse
<p>I demonstrated this recursion example in class. I draw a large square on the board and ask a student to picture it like a 3x3 grid (like Tic-Tac-Toe). Then the student outlines the center square. Next, the student looks at the other eight squares and repeats the process in each of them. And so on. And so on. That illustrates the process. If you do this in a program, you get the window below. And here's a Java program I wrote to create that window: <a href="https://github.com/CoachEd/JavaExamples/blob/master/Recursion/Squares.java" rel="noreferrer">Squares.java</a>.  </p>

<p><a href="https://i.sstatic.net/sJLvK.png" rel="noreferrer"><img src="https://i.sstatic.net/sJLvK.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2018-01-13T07:17:27.673Z
Good, but that's not really an *analogy.*
Wildcard
CC BY-SA 4.0
2019-06-10T21:26:23.467Z
is there an end state?
pluke
CC BY-SA 4.0
2020-08-26T17:47:42.400Z
A Sierpinski Carpet certainly looks cool and helps explain the concept, but it's unlikely that students are going to be able to code it (or understand code you give them) as their very first recursion project. There are too many recursive calls and computing the locations is likely non-intuitive for a beginner. It might be suitable as part of a graphics-focused CS basics course in Scratch or P5, but even here, it's probably a third or fourth project rather than the first. I remember struggling with a simplified version of this project quite a bit in my second CS course.
ggorlen
CC BY-SA 4.0
2021-09-03T10:36:45.463Z
@pluke: Mathematically, there is no end state. However, you can introduce one computationally, whereby your image generating algorithm stops once the squares are smaller than a pixel and therefore make no visual difference anymore anyway.
Flater
CC BY-SA 3.0
2017-06-29T20:01:03.087Z
2017-06-29T20:01:03.087Z
Edwin Torres
<p>Rather than use an analogy, you could give a real world example. The way a tree grows, the shell of a snail, the petals on a sunflower. I believe these are all fine examples - the same solution applied over and over again to a problem until a base case is reached (such as a lack of resources or a height limit at which point water can't be delivered to the leaves)</p>

CC BY-SA 3.0
2017-06-08T04:50:45.853Z
I think students are _surprised_ and _fascinated_ to see the pattern of a recurrent arithmetic sequence emerge in nature (e.g., the Fibonacci sequence in the petals on a sunflower).  I don't think this taps into any deep intuition for them. So, to say "if you want to understand recursion, just reflect on the natural processes around you that have surprising recurrent properties..." may not be helpful.
GermaneDork
CC BY-SA 3.0
2017-05-23T15:15:29.930Z
Hi Marc, I like these, can you expand on how you would use any of these? For example (and rather simply) the tree: for branch, if water available, grow branch, split branch in two.
pluke
CC BY-SA 3.0
2017-05-23T17:02:46.257Z
Your examples are missing a purpose. It may seem obvious, but I'm not sure the snail shell example works as well as 'fill a volume of soil with uniform root density'
Sean Houlihane
CC BY-SA 3.0
2017-05-23T15:08:55.050Z
2017-05-23T15:08:55.050Z
Marc Scott
<p>To make for a hands-on demonstration, I brought in a set of my son's Mega Bloks:</p>

<p><a href="https://i.sstatic.net/DHjAV.jpg" rel="noreferrer"><img src="https://i.sstatic.net/DHjAV.jpg" alt="Mega Bloks"></a></p>

<p>I slowly built up a stack of blocks, and using a dry-erase marker, wrote the calling function and its argument on the block itself. With each new call, I "pushed" the function call onto my stack and then "popped" them off one by one as the functions began to return values rather than more function calls.</p>

<p>I used a basic factorial problem, so my stack of blocks ended up looking something like this:</p>

<pre><code>--factorial(1)--
--factorial(2)--
--factorial(3)--
--factorial(4)--
--   main()   -- 
</code></pre>

<p>Students could see how one call to factorial relied on other calls and so on until reaching the base case which "tore down" the stack we had just built.</p>

<p>One of the magical elements of recursion for students is how a function can call itself. The idea of return values and a growing stack of function calls at least gave a tangible and visual example for something that can be abstract and initially challenging to understand.</p>

CC BY-SA 3.0
2017-05-23T16:02:37.253Z
2017-05-23T16:02:37.253Z
Peter
<p>I bought a set of nested Russian dolls (Matryoshka dolls).</p>

<ol>
<li><p>Show the assembled set - how many dolls are there? We don't know, but maybe there is one inside - take a look</p></li>
<li><p>Yes, now how many dolls? We don't know, but maybe there is one inside... </p></li>
<li><p>Repeat until there is not a doll inside - this is the bottom of the stack. </p></li>
<li><p>Now reassemble the stack, counting the dolls as you go.</p></li>
</ol>

CC BY-SA 4.0
2021-09-03T10:33:07.977Z
"Repeat until" suggests that there is no need for recursion in this example, which there indeed isn't here. Your analogy is perfectly encapsulated by e.g. a linked list, which does not require recursion to traverse.
Flater
CC BY-SA 3.0
2017-05-24T00:57:57.477Z
2017-05-25T05:06:19.803Z
2017-05-25T05:06:19.803Z
Kapai
<p>Although there already is many great answers, one analog I found helpful was the dictionary lookup analogy (this is different than the dictionary binary search analogy). It goes like this:</p>

<p>Lets say you want to know what the word "long" means. You look up the word in dictionary.com find that it means "having considerable linear extent in space." Lets say for the sake of example that you do not know what "linear" and "extent" means. Then you would look up those words definitions. If theres any word in those definitions that you don't know, you would look that up in the dictionary and so on. </p>

<p>In code, it'll look something like this:</p>

<pre><code>public static void lookupInDictionary(String word){
   String definition = getDefinition(word);
   if(understandsAllWordsIn(definition)){
       return;
   } else {
       for(String word: wordsNotUnderstood(definition)){
           lookupInDictionary(word);
       }
   }
}
</code></pre>

<p>You can also use this to teach infinite recursion. Lets say this was the dictionary:</p>

<pre>
Hello: Hi
Hi: Hello
</pre>

<p>If one tried to call <code>lookupInDictionary("Hello")</code> or <code>lookupInDictionary("Hi")</code>, it would recurse infinitely.</p>

CC BY-SA 3.0
2017-07-01T18:40:15.167Z
That's a clever little example.  :)  Welcome to [cseducators.se]. I hope we hear more from you in the future!
Ben I.
CC BY-SA 3.0
2018-01-13T07:18:38.930Z
Good one!  And if you get a stack overflow, it's time to get a simpler dictionary and start over!
Wildcard
CC BY-SA 3.0
2017-07-01T18:31:03.850Z
2017-07-01T18:48:08.057Z
2017-07-01T18:48:08.057Z
DumboOctopus
<p>Rather than use analogy, I think it best to demonstrate the power of recursion on a problem for which the recursive solution is natural and the alternative solutions are an obvious exercise in masochism, to write and especially to prove. Take the Towers of Hanoi problem. When one sees how the problem just cleaves and dissolves into the recursive formulation, that experience of awe will drive one to a deeper and more nuanced exploration of recursion. Elegant expression requires no analogy.</p>

CC BY-SA 3.0
2017-05-23T17:24:00.510Z
2017-05-24T02:06:36.360Z
2017-05-24T02:06:36.360Z
Andrew Sundstrom
<p>I think a computational joke is in order to help students get started.</p>

<p>All numbers are interesting, for a function $F()$</p>

<p>$F(0)$ is interesting because it's the first number.
$F(F(0))$ i.e. 1 is interesting because it's either interesting or if not interesting is the first non-interesting number and therefore interesting. $$F(F(F(0)))$$ is interesting because...</p>

CC BY-SA 3.0
2017-06-14T18:37:26.533Z
This looks like [Church Numerals](https://en.wikipedia.org/wiki/Church_encoding) to me. =/
Ben I.
CC BY-SA 3.0
2017-06-14T18:35:17.247Z
2017-06-14T19:13:50.963Z
2017-06-14T19:13:50.963Z
Dominic Connor Quant Headhunt
<p>A fairly deep example of a recursive process that has some serious issues that might be discussed with students is as follows. </p>

<p>Suppose that you are a doctoral student in mathematics beginning your dissertation studies. Your advisor has given you a topic to explore, but you know little about it in detail. The advisor suggests a research article as a place to start. The process is: </p>

<p>If the article is by Euclid, read it and you are done. </p>

<p>However, if it isn't by Euclid, then after you read it you will not likely understand everything, so (recursively) read all of the articles in that article's bibliography. However, if you <em>do</em> understand everything already, there is no need to pursue the bibliography. </p>

<p>This process (read and chase bib) proceeds until you understand everything you've read or until you reach Euclid. </p>

<hr>

<p>This process is actually closer to the truth than you might expect, but it has at least one (maybe two) serious flaw. After describing the process to students (even relative beginners), ask for their help in identifying the flaw(s). This can lead to a deeper understanding of recursion than a simple (flawless) example. </p>

CC BY-SA 3.0
2018-01-13T07:22:36.500Z
Interesting starting point for discussion.  It bears mentioning that a much more effective way to *actually* understand an article is to clear up every *word* you encounter that you don't understand, *when* you encounter it, and not go on past a misunderstood word *at all.*  But that's not an example of recursion (just the most important rule of study).
Wildcard
CC BY-SA 3.0
2018-01-10T14:28:42.217Z
2018-01-10T14:28:42.217Z
Buffy
<p>This is an old question with lots of answers, but a new one just occurred to me: long division. The benefit here is that most students will already be familiar (and hopefully comfortable) with the mechanics of it, so "recursion" is just another way to talk about something that's already familiar.</p>

CC BY-SA 4.0
2018-07-26T17:53:57.427Z
Good one!! Never thought about it before.
Failed Scientist
CC BY-SA 4.0
2018-07-25T18:12:41.197Z
2018-07-25T18:12:41.197Z
G. Ann - SonarSource Team
<p>A new answer for this came to me today. Infinite indirect recursion:</p>
<blockquote>
<p>Pete and Repete are in a tree. Pete falls out. Who's left?</p>
</blockquote>

CC BY-SA 4.0
2022-06-07T18:12:48.647Z
2022-06-08T19:25:13.250Z
2022-06-08T19:25:13.250Z
G. Ann - SonarSource Team
<p>Google recursion. </p>

<p><a href="https://i.sstatic.net/BIFA7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/BIFA7.png" alt="enter image description here"></a></p>

<p>It's a recursive link! Ah, google easter eggs...</p>

<p>Then, you can maybe give them a problem that depends on recursion - like, say, a multiplication algorithm of some sort (I saw one somewhere that used recursion and was pretty simple - I'll edit to add it if I find it) to give a more programming oriented example. </p>

CC BY-SA 3.0
2017-06-17T15:47:46.587Z
2017-06-17T15:47:46.587Z
auden
<p>I hesitated to answer since most of the answers given are already so good. However, I've also used <a href="https://en.wikipedia.org/wiki/There_Was_an_Old_Lady_Who_Swallowed_a_Fly" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/There_Was_an_Old_Lady_Who_Swallowed_a_Fly</a> as an introduction, though it isn't precisely recursive. It is more focused on a list as a stack, which leads naturally to recursion. </p>

<p>In my class we occasionally had "Choir Practice" in which I'd ask a number of students to participate in various "games." For this exercise I'd give each of them a Script card. Starting with only myself and one student, I'd do one verse of the poem, then "push" another student on to the stack and continue. </p>

<p>I start (with one student) and say:</p>

<pre><code>There was an old woman who swallowed a fly,
</code></pre>

<p>I then point to the one student who reads his/her script card. The first says:</p>

<pre><code>I don't know why she swallowed a fly, Perhaps she'll die.(Take a bow.)
</code></pre>

<p>Then, "pushing" the second student (now I have a stack of two), I'd say:</p>

<pre><code>There was an old woman who swallowed a spider, That wriggled and jiggled and tickled inside her,
</code></pre>

<p>I'd point to the (new) stack top who would read the script:</p>

<pre><code>She swallowed the spider to catch the fly, (point to the next person)
</code></pre>

<p>etc for as long as you like. "Pointing" to a person is passing them the message to read (sing-act) their own script. </p>

<p>Depending on how you talk about the exercise you can use it to reinforce lists, stacks and/or recursion. Note the base case (...take a bow). The "message" sent is recursive, though. You can also explore what happens without a base case in your follow up discussion. </p>

<p>A bit foolish, but my University students tended to like it even if they did roll their eyes a bit. </p>

<p>Note that such "active learning" exercises always require follow up discussion in which you point to the mapping between the elements of the game and the lesson to be learned and students get to unwind any puzzlement. </p>

<hr>

<p>Here is a <a href="https://drive.google.com/open?id=0B8yuv5DJXhC7b255aEE5SExkSlk" rel="nofollow noreferrer">link to the card deck</a></p>

CC BY-SA 3.0
2017-06-30T12:19:37.620Z
2017-06-30T15:55:25.060Z
2017-06-30T15:55:25.060Z
Buffy
<p>When I was first taught recursion in a high school CS class, the teacher had us read a short story called <strong>Martin and the Dragon</strong>, found in chapter 8 of "Common LISP: A Gentle Introduction to Symbolic Computation" by David S. Touretsky. In the story, a boy named Martin visits an unruly dragon and uses recursive techniques to coerce it into helping him with a few different computational tasks that are common in LISP, including iterating over a list, calculating a factorial, counting, and calculating fibonacci numbers (which also teaches infinite recursion).</p>

<p>A shorter analogy might be a multi-level marketing scheme - it starts with one person, who has to recruit several more, who each in turn have to convert a few others, and so on.</p>

<p>Genealogical lines are also a naturally recursive data structure - you have two biological parents, who in turn each have two biological parents, and so on and so forth. It can also work for children and/or other species. </p>

CC BY-SA 3.0
2018-01-10T11:37:51.110Z
Welcome to CSEducators. We hope you come back often. Could you expand your first paragraph a bit to give at least a hint about _which_ recursive techniques.
Buffy
CC BY-SA 3.0
2018-01-10T09:02:18.097Z
2018-01-10T16:50:58.407Z
2018-01-10T16:50:58.407Z
Kendra
<p>My first practical use of recursion was to work out the total weight of a bunch of containers (portage packs and the various stuff sacks and whatnot inside them.) You know that the blue bag holds the green bag and the tent. You know what the tent weighs. You know that the green bag holds the red bag and the brown bag. Etc.</p>

<p>Similar problems include the "salary burden" of a VP who has several departments under them, and each department has a department head with teams under them, and so on, but without a strict hierarchy so some departments have no teams, just everyone reporting to the head, and some people report directly to the VP but don't head a department, etc. You could also do revenue within a large company the same way. Or inventorying your personal possessions.</p>

CC BY-SA 3.0
2017-10-06T12:34:48.373Z
Not everything is a tree, but good examples: Trying to organise everything as a tree, such as a company, does not work to produce well functioning organisations. See “a city is not a tree” — Christopher Alexander.
ctrl-alt-delor
CC BY-SA 3.0
2017-10-06T13:24:45.490Z
I would never argue with the author of one of my favourite books, but the point was that someone else set the company up like that and now you need to make certain calculations on it like "what do we spend on R&D?" and recursion is a way to do that calculation. Since we are just looking for good examples, whether they in fact represent best practices in the real world of running companies isn't super relevant.
Kate Gregory
CC BY-SA 3.0
2017-10-06T11:59:10.450Z
2017-10-06T11:59:10.450Z
Kate Gregory
<p>Came across this one. I simply loved it:</p>

<blockquote>
  <p><a href="https://en.wikipedia.org/wiki/Hofstadter%27s_law" rel="nofollow noreferrer">Hofstadter's Law</a>: It always takes longer than you expect, even when you take into account Hofstadter's Law.</p>
</blockquote>

<p>This is especially good when explaining debugging a recursive method, or the call stack. When you reach the end of the sentence, you go to the definition of Hofstadter's Law (If you are a compiler). And this goes on and on (essentially a stack overflow).</p>

CC BY-SA 3.0
2017-06-29T18:45:31.720Z
2018-01-14T19:50:55.080Z
2018-01-14T19:50:55.080Z
ItamarG3
<p>You're working in an office. If a question comes up, the first person you consult is yourself. If the person to consult doesn't know the answer, they consult their manager, and upon receiving the answer pass it down the hierarchy again. Recurse until you have the answer.</p>
<p>So:</p>
<pre><code>ask( person from, person to ):
  if not: from knows the answer
     ask( from's manager, from )
  tell( from, to )
</code></pre>
<p>and invoke this with</p>
<pre><code>ask(me,me)
</code></pre>
<p>(You still have to define <code>tell(from,to)</code> and make sure that's a no-op if <code>from==to</code>.)</p>
<p>I like this example because it is not trivially iteratable as tail recursion. This explicitly goes up and down the stack.</p>
<p>Next step: if you ask something of someone, you take out a notepad to record what they tell you. If that person doesn't know, they take out a notepad and ask further. Now you know where stack overflow comes from: there is a bunch of notepads open simultaneously, and they all take up some amount of memory.</p>

CC BY-SA 4.0
2022-02-16T02:23:42.097Z
The image of each person taking out a notepad just reminds me of Dr Seuss somehow. He had some things that were self-referential in his stories, I think. Very visual and memorable.
Scott Rowe
CC BY-SA 4.0
2022-02-16T03:27:13.780Z
Like https://2.bp.blogspot.com/-G5cMV3yjXCU/VOyZkzIYGlI/AAAAAAAAHMc/yJmT_WHduqs/s1600/51kRVqJxa3L.jpg ?
Victor Eijkhout
CC BY-SA 4.0
2022-02-16T11:04:55.243Z
"Oh, no you don't, Mr Feynman! It's turtles all the way down." I had some of those books as a child. Others I saw at the pediatrician's office. Yes. Pretty brilliant. We need more teaching like that. And Mr Rogers...
Scott Rowe
CC BY-SA 4.0
2022-02-14T18:16:30.653Z
2022-02-15T20:23:17.307Z
2022-02-15T20:23:17.307Z
Victor Eijkhout
<p>Pretty late to see this. Thought to add my two cents as well.</p>

<p>Recursion simply reminds me of the barber shop (provided he has parallel mirrors on either side of you) where we used to observe the array of mirrors (<em>Fun Fact: once even counted them uptil 83 until they were no more visible</em>). Also, during matches, when often cameraman used to pan at the giant-screen and we used to see the array of screens in it (all recursively).</p>

CC BY-SA 4.0
2018-07-27T00:26:57.937Z
Recursion with no base case!  :)
Ben I.
CC BY-SA 4.0
2018-07-27T04:34:07.280Z
Haha point. Can we count the skewness of reflection angle or minimum size as base case? Just a thought came to my mind in reply to your golden point.
Failed Scientist
CC BY-SA 4.0
2018-07-26T17:53:09.767Z
2018-07-26T17:53:09.767Z
Failed Scientist
<p>I think there are two separate aspects to understanding recursion:</p>

<ol>
<li>How to use recursion to solve problems</li>
<li>How recursion is evaluated</li>
</ol>

<h2>How to use recursion</h2>

<p>Let's look at an example: maximum depth of a binary tree (where a tree with a single node is depth 1). A recursive solution in python might look like this:</p>

<pre><code>def max_depth(root):
  if root is None:
    return 0

  return 1 + max(max_depth(root.left), max_depth(root.right))
</code></pre>

<p>You don't need to think about how this is actually evaluated; you just define it how you would mathematically. If I <em>somehow</em> know that the maximum depth of the left branch is $x$ and the maximum depth of the right branch is $y$ and that $x &gt; y$ (without loss of generality), then I know that the maximum depth of the entire tree is $1 + x$. This way of thinking about problems is one way you can use recursion.</p>

<p>Of course, you need to make sure that the inputs to the recursive calls are in some way smaller than the input to the function that makes the recursive call, which segues into how recursion is evaluated.</p>

<h2>How recursion is evaluated</h2>

<p>To think about how recursion is evaluated, we can use the same example. In the example above, there are pending recursive calls, waiting to return (note that recursion does not necessarily have this, see <a href="https://en.wikipedia.org/wiki/Tail_call" rel="nofollow noreferrer">tail call</a>). To see this, suppose our tree looks like this</p>

<pre><code>    O &lt;- root
   / \
  O   O
 / \
O   O
</code></pre>

<p>and you have a variable r storing the root. If you call <code>max_depth(r)</code>, it will try to evaluate the else clause; it will evaluate <code>max(max_depth(r.left), ...)</code> and then add 1 to that result. To the <code>r.left</code> recursive call, the input looks like this</p>

<pre><code>     O
    / \
   O   O
</code></pre>

<p>And for the <code>r.right</code> recursive call, it is simply this:</p>

<pre><code>O
</code></pre>

<p>The <code>r.left</code> recursive call evaluates else clause, which means it tries to evaluate the max depth of the left and right subtrees, and add 1 to whichever is greater.</p>

<p>The <code>r.right</code> recursive call also evaluates the else clause.</p>

<p>So at this point you think of the return value of the original call to max_depth looking like this:</p>

<pre><code>return 1 + max(
               1 + max(max_depth(root.left.left), max_depth(root.left.right),
               1 + max(max_depth(root.right.left), max_depth(root.right.right))
              )
</code></pre>

<p>Both recursive calls of the left branch have trees that look like this now</p>

<pre><code>O
</code></pre>

<p>while both recursive calls of the right branch, since it was just a node without any children, have trees that are empty, which is <code>None</code> in Python. Thus, they fall to the base-case, which means it is evaluated as 0.</p>

<p>So now the original return value is like this</p>

<pre><code>return 1 + max(
               1 + max(
                       1 + max(max_depth(root.left.left.left), max_depth(root.left.left.right)),
                       1 + max(max_depth(root.left.right.left), max_depth(root.left.right.right))
                      ),
               1 + max(
                       0,
                       0
                      )
              )
</code></pre>

<p>All recursive paths from the right branch already reached the base-case, and now on this recursive call, all children of the left branch will as well, which means the return value of the original function is now</p>

<pre><code>return 1 + max(
               1 + max(
                       1 + max(
                               0,
                               0
                              ),
                       1 + max(
                               0,
                               0)
                      ),
               1 + max(
                       0,
                       0
                      )
              )
</code></pre>

<p>which evaluates to</p>

<pre><code>return 1 + max(
               1 + max(
                       1 + 0,
                       1 + 0
                      ),
               1 + 0
              )
</code></pre>

<p>and</p>

<pre><code>return 1 + max(
               1 + 1,
               1 + 0
              )
</code></pre>

<p>and</p>

<pre><code>return 1 + 2
</code></pre>

<p>finally</p>

<pre><code>3
</code></pre>

<p>Note, this evaluation was not performed according to any formal evaluation model (see <a href="https://www.cs.cornell.edu/courses/cs3110/2013sp/lectures/lec06-subst-model/lec06.html" rel="nofollow noreferrer">substitution model</a> or <a href="https://berkeley-cs61as.github.io/textbook/the-environment-model-of-evaluation.html" rel="nofollow noreferrer">environment model</a>); it was merely to help build intuition for how evaluation could be done.</p>

<p><strong>Extra (tail-recursion)</strong>: I mentioned earlier about how recursion does not necessarily have these pending function calls that must be recursed back to once they finally have the result of the recursive call. Consider a recursive function to find the sum of a list (ignoring the python built-in <code>sum()</code>):</p>

<pre><code>def sum_list(lst):
  if lst == []:
    return 0

  return lst[0] + sum_list(lst[1:])
</code></pre>

<p>This indeed would have pending recursive calls, as it waits to add lst[0] to the result of the recursive calls. We can make this tail-recursive by accumulating the sum of the list in an argument that is simply returned unmodified at the end:</p>

<pre><code>def sum_list_tail_recursive(lst, result):
  if lst == []:
    return result

  return sum_list_tail_recursive(lst[1:], result + lst[0])
</code></pre>

<p>Once this evaluation reaches the base-case, it has the the result of the original call to <code>sum_list()</code>, and it does not need to be added to, or modified in any way as you recurse back up, and so if a compiler/interpreter recognizes this, it can optimize by skipping directly to the first call, eliminating the need to recurse back to it step-by-step.</p>

CC BY-SA 4.0
2018-05-05T12:02:28.717Z
2018-07-27T22:48:28.663Z
2018-07-27T22:48:28.663Z
Samasambo
<p>Here is my cake-baking analogy:</p>
<p>Suppose the recipe for a 3-layer cake said &quot;first bake a 2 layer cake, then add flour, sugar, and butter, and put it in the oven&quot;.</p>
<p>And the recipe for the 2-layer cake says &quot;first bake a 1 layer cake, then add flour, sugar, and butter, and put it in the oven&quot;.</p>
<p>But once you get to the 1-layer cake, that's it. You've reached the base case. The buck stops there. Unlike the recipes for the 2-or-more-layers cakes, the recipe for the 1-layer cake doesn't refer to any other recipes.</p>
<p>I think this analogy captures the concept of the base case (the 1-layer cake) and the recursive step (add sugar, flour, and butter then bake).</p>

CC BY-SA 4.0
2021-09-11T21:41:24.573Z
2021-09-11T21:41:24.573Z
1f604
<p>You can do some stuff with the filesystem<br>
like. start with a folder and count all files in it<br>
or let them create a overview of folders and files</p>

CC BY-SA 4.0
2018-05-04T15:22:26.157Z
2018-05-04T15:22:26.157Z
dwana
<p>I came up with an analogy that helped me visualize recursive programming a great deal.</p>

<ol>
<li>Imagine a water tank with an inflow pipe on one side. On the other side, about halfway up the tank, is the outflow pipe which is where you collect the water.</li>
<li>Water enters the inflow pipe. As it enters, it gets tested to see if it's clean. If it's found to be clean, a valve will empty the water directly into the tank and let the clean water flow into the tank and then right through to the outflow pipe and we are done.</li>
<li>But if the water test reveals that it is dirty, it gets decontaminated by some amount then gets directed into another tank inside of bigger tank.</li>
<li>This second tank does exactly the same thing as the outer tank. It first tests the water, dumps it into the tank if it is clean and if it isn't, it cleans it a little bit, and then sends it to a third inner tank. This process continues.</li>
<li>When the last inner tank is reached and the water is completely clean, the valve lets the water spill directly into the tank. This water then flows out of the tank though the outflow and into the outer tank surrounding it. That outer tank fills up until water spills out into <em>its</em> outer tank. Each of these tanks can also treat the water if they want (add chlorine or fluoride to it or even send it to another recursive processing tank).</li>
<li>This cascading action continues until the last outer tank spills out the clean, processed water, representing the data we desire.</li>
</ol>

CC BY-SA 4.0
2018-09-08T11:16:20.973Z
This seems like an overly complex way to clean water.
ctrl-alt-delor
CC BY-SA 4.0
2018-09-13T02:15:09.737Z
@ctrl-alt-delor Actually, except for the placement of the tanks, this is not far off from the real process. Water is treated in one tank, then another, then another, and so forth until it is clean. At least in NYC, the last "tank" is really an ecosystem. It is a biocleaning using algae, and many animals eat the algae, many animals eat those animals, and so forth. On the radio, they said it is actually quite beautiful in there.
Ben I.
CC BY-SA 4.0
2018-09-07T22:58:09.950Z
2018-09-07T23:04:28.387Z
2018-09-07T23:04:28.387Z
StevieD
<p>Maybe you can start by showing a clip of <em>Groundhog Day</em>. Explain how his days are constantly in the same loop, and the loop does not end until he "fixes" something.</p>

<p>Which in programming would be considered a <code>base case</code>.</p>

CC BY-SA 3.0
2017-09-22T20:00:05.257Z
Seems a bit weak, actually. Where is the recursive "call"? Might be better for `while loops` where you also need a stopping condition.
Buffy
CC BY-SA 3.0
2017-09-22T19:56:13.343Z
2017-09-22T23:09:08.623Z
2017-09-22T23:09:08.623Z
Shams Ali
<p>I thought of repetitive song lyrics, initially the <a href="https://www.youtube.com/watch?v=0U2zJOryHKQ" rel="nofollow noreferrer">Song That Never Ends</a> - a good example of infinite recursion. Then came to mind <a href="https://www.youtube.com/watch?v=T0ooQv7oHvw" rel="nofollow noreferrer">Ten Green Bottles</a>, which I think is a nice simple illustration with a clear base case and inputs that keep reducing, ultimately to the base case.</p>

CC BY-SA 4.0
2018-05-04T14:32:26.877Z
2018-05-04T14:32:26.877Z
germ
<p>When teaching recursion, what is the best analogy people use to teach the idea of recursion. There are some <a href="https://en.wikipedia.org/wiki/Droste_effect" rel="noreferrer">nice artistic representations</a> </p>

<p><a href="https://i.sstatic.net/XUyAr.jpg" rel="noreferrer"><img src="https://i.sstatic.net/XUyAr.jpg" alt="enter image description here"></a></p>

<p>And the idea of repeatedly cutting a phone book or dictionary in half until you find a number/word (basically binary search). The only problem is students don't use phone books/paper dictionaries anymore and the artistic representation doesn't imply an end goal/state.</p>

CC BY-SA 3.0
2017-07-03T23:43:54.457Z
curse = to abuse something verbally.  recurse = to repeat oneself while abuse something verbally
pojo-guy
CC BY-SA 3.0
2017-07-21T12:06:51.367Z
You've ordered things, and you receives a parcel. It is a cardbox containing things, some of them are enclosed in cardboxes. Boxes may contain other (obviously smaller) cardboxes.
Michel Billaud
CC BY-SA 3.0
2017-07-21T12:07:52.410Z
You've posted a message, which now has other messages as answers. Answer themselves may have answers, etc.
Michel Billaud
CC BY-SA 3.0
2017-05-23T15:02:26.913Z
Do you have any specific language you are using?
Manav Dubey
CC BY-SA 3.0
2017-05-23T15:03:14.630Z
This is language agnostic, I'm really looking forward to ways for students to grasp the concept of recusion
pluke
CC BY-SA 3.0
2017-05-23T15:08:45.480Z
How about [Fractals](https://en.wikipedia.org/wiki/Fractal)?
Quazi Irfan
CC BY-SA 3.0
2017-05-23T15:09:31.047Z
Fractals are nice, but it doesn't get away from my problem of not having an end state / goal
pluke
CC BY-SA 3.0
2017-05-23T15:27:21.753Z
Wait, what's recursion again?  Okay, [Google "recursion"](https://www.google.com/?gws_rd=ssl#q=recursion)... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Opps, out of characters - stack overflow!
Nat
CC BY-SA 3.0
2017-05-23T20:25:03.307Z
You may find [this discussion](https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion) helpful.
Miles
CC BY-SA 3.0
2017-05-28T16:17:34.910Z
There is a question about recursion here https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion
ctrl-alt-delor
CC BY-SA 3.0
2017-06-02T15:34:46.397Z
This was a great question. I hope we hear more from you!
Ben I.
CC BY-SA 3.0
2018-01-14T04:56:52.130Z
There are lot's of good suggestions below. I would suggest using an example that does not admit an easy iterative solution. Bonus points if it does not use tail-recursion.
Jive Dadson
CC BY-SA 4.0
2018-05-06T22:13:05.503Z
Find the file named "ThisIsIt" but only if it is at the bottom-most node of a tree-structured directory.
Bob Brown
CC BY-SA 4.0
2018-09-08T11:13:39.070Z
It is like teaching recursion.
ctrl-alt-delor
CC BY-SA 4.0
2018-09-18T16:02:58.870Z
A recursive program is a program that calls itself recursively.
JosephDoggie
CC BY-SA 3.0
2017-10-06T13:43:59.853Z
To teach recursion, I first teach iteration, then I teach recursion.
Michel Billaud
CC BY-SA 4.0
2020-08-26T17:51:02.867Z
Related thread (no, this is not a recursive link to the same thread) over at CS SE: [teaching recursion](https://cs.stackexchange.com/questions/30712/teaching-recursion)
ggorlen
CC BY-SA 4.0
2021-09-07T13:57:03.917Z
Well people wrote a lot of ideas, I'll just remind of the simple Fibonacci Series as it doesn't involve programming just the recursion concept in a simple form; and they already took it in high school without the emphasize on the recursion concept
ShAr
<recursion><teaching-analogy>
Analogy for teaching recursion
# Analogy for teaching recursion

(Asked by: username_0 on 2017-05-23)

When teaching recursion, what is the best analogy people use to teach the idea of recursion. There are some [nice artistic representations](https://en.wikipedia.org/wiki/Droste_effect)

[![enter image description here](https://i.sstatic.net/XUyAr.jpg)](https://i.sstatic.net/XUyAr.jpg)

And the idea of repeatedly cutting a phone book or dictionary in half until you find a number/word (basically binary search). The only problem is students don't use phone books/paper dictionaries anymore and the artistic representation doesn't imply an end goal/state.

**Tags:** recursion, teaching-analogy

> **Comments:**
> **username_3**: Do you have any specific language you are using?  
> **username_0**: This is language agnostic, I'm really looking forward to ways for students to grasp the concept of recusion  
> **username_4**: How about [Fractals](https://en.wikipedia.org/wiki/Fractal)?  
> **username_0**: Fractals are nice, but it doesn't get away from my problem of not having an end state / goal  
> **username_5**: Wait, what's recursion again?  Okay, [Google "recursion"](https://www.google.com/?gws_rd=ssl#q=recursion)... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Okay, clicking that... huh, it gives "_Did you mean: [recursion](https://www.google.com/?gws_rd=ssl#q=recursion)_"?  Opps, out of characters - stack overflow!  
> **username_6**: You may find [this discussion](https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion) helpful.  
> **username_7**: There is a question about recursion here https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion  
> **username_8**: This was a great question. I hope we hear more from you!  
> **username_1**: curse = to abuse something verbally.  recurse = to repeat oneself while abuse something verbally  
> **username_2**: You've ordered things, and you receives a parcel. It is a cardbox containing things, some of them are enclosed in cardboxes. Boxes may contain other (obviously smaller) cardboxes.  
> **username_2**: You've posted a message, which now has other messages as answers. Answer themselves may have answers, etc.  
> **username_2**: To teach recursion, I first teach iteration, then I teach recursion.  
> **username_9**: There are lot's of good suggestions below. I would suggest using an example that does not admit an easy iterative solution. Bonus points if it does not use tail-recursion.  
> **username_10**: Find the file named "ThisIsIt" but only if it is at the bottom-most node of a tree-structured directory.  
> **username_7**: It is like teaching recursion.  
> **username_11**: A recursive program is a program that calls itself recursively.  
> **username_12**: Related thread (no, this is not a recursive link to the same thread) over at CS SE: [teaching recursion](https://cs.stackexchange.com/questions/30712/teaching-recursion)  
> **username_13**: Well people wrote a lot of ideas, I'll just remind of the simple Fibonacci Series as it doesn't involve programming just the recursion concept in a simple form; and they already took it in high school without the emphasize on the recursion concept  

---

## 30 answers

### Answer by username_14 on 2017-05-23. Score: 15 | Accepted answer

I like to use something that a student can connect with and something that they have to deal with regularly. You could choose any recursive everyday activity, but I like to choose revising an essay.
Let's say you've already written your essay, and now you want to go back and perfect it. First you read the essay again, then you get feedback from others, then you make the changes, and then you revise the essay unless you consider your essay complete. In pseudocode:
function revise(essay) {
  read(essay);
  get_feedback_on(essay);
  apply_changes_to(essay);
  revise(essay) unless essay.complete?;
}

After the students understand the basics of what recursion is by following the simple example above or one like it, I'd move on to more sophisticated examples of recursion like a simple sort. Take merge sort for example (this assumes arrays have been taught):
function sort(array) {
  a = array.first_half;
  b = array.second_half;
  sort(a);
  sort(b);
  merge(a,b);
}

function merge(a,b) {
  final = [];
  a_counter = 0;
  b_counter = 0;
  while (final.length < a.length*2) {
    if a[a_counter] < b[b_counter] {
      final.push(a.shift);
      a_counter++;
    } else if (b[b_counter] < a[a_counter]) {
      final.push(b.shift);
      b_counter++;
    }
  }
  return final;
}

> **Comments:**
> **username_15**: You've shown tail-recursion on a problem of the same size at each function invocation, and have thus merely reformulated a `do {...} until` block. This doesn't demonstrate the general power of recursion. To keep with your example, I prefer a formulation like this:  `function revise(essay) {     if essay.scale > sentence {         foreach s in essay.subsections {             revise(s);         }     }     do {         read(essay);         get_feedback_on(essay);         apply_changes_to(essay);     } until essay.complete? }`  
> **username_16**: The first one is just a loop...  

---

### Answer by username_6 on 2017-05-24. Score: 30

The [Tower of Hanoi](https://en.wikipedia.org/wiki/Tower_of_Hanoi) was one of the first ways that I encountered recursion.

[![Tower of Hanoi, cc by-sa Bin im Garten](https://i.sstatic.net/dEbk3.png)](https://i.sstatic.net/dEbk3.png)

"The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk." (from Wikipedia)

To solve the n disk tower problem:

1. Solve the n-1 disk tower problem
2. Move the nth disk
3. Solve the n-1 disk tower problem again.

Solving the 1 disk problem is trivial.

I can imagine coding this as a nice on-screen or physical computing challenge.

> **Comments:**
> **username_18**: Yes! I remember seeing this on an educational TV programme in Germany, and I found this so elegant. I was then very disappointed when I realised that the BASIC dialect that I used did not support recursion (directly). Well, it was a reason to learn Pascal later :)  
> **username_19**: I find this a really good example because — unlike many of the other examples — this one _can't_ be seen as a fancy way of writing an iterative algorithm.  

---

### Answer by username_20 on 2017-06-18. Score: 20

Can't claim it's my own idea but I can embellish it a little...

Imagine you are entering a cinema. You sit down in a row but realise you had to sit in row 20. Being a lazy computer scientist in an already full theatre of other computer scientists (they're all there watching War Games again) you decide to recursively determine your row.

You ask the person in front. Trouble is they didn't check either. So again being lazy they ask the person in front of them. This continues until the bottom row is reached. This person knows they are in row 1 (they are there with a computer scientist friend but they aren't a computer scientist so they start counting at 1 not 0).

This is passed back to the person who asked, who being a computer scientist can add 1 to the number this person told them. This carries on until the original person asking finds out that the row in front of them is 31 and that must mean they are in 32.

He doesn't move though as he converts the value to hex to convince himself that it is row 20. He likes efficiency!

*Cheo, C. (2015). 40 Key Computer Science Concepts Explained In Layman’s Terms. [Online] Available at: <http://carlcheo.com/compsci>*

> **Comments:**
> **username_8**: Nice, with a cute ending :)  
> **username_21**: Glad it's a computer scientist and not an anthropologist. Otherwise the hex conversion would be cause for using a counter-curse.  

---

### Answer by username_22 on 2017-05-24. Score: 16

The image that I kept in my head when I was learning recursion was from Dr. Seuss:
[![enter image description here](https://i.sstatic.net/NFZVv.jpg)](https://i.sstatic.net/NFZVv.jpg)

> **Comments:**
> **username_22**: Downvote with no comment? The OP asked for an _analogy_. IMO the Cat in the Hat's Little Cats are a perfect analogy.  
> **username_7**: Do all cats in the hat, have a cat in their hat?  
> **username_23**: I like that this is imperfect as an analogy, gives scope for discussion.  
> **username_24**: @richard no. they don't need to. otherwise you get stackoverflow.  
> **username_7**: @ItamarGreen but as can be seen from the image, the stack is a cat stack. If every can in a hat had a cat in there hat, then the stack would not overflow, because it would be infinite. This could lead to a very tall stack of cats, but as each cat is getting smaller. it may be asymptotic. For example if each cat was half the size of the one bellow then the hight for an infinite number of cats would be 2×size_of_bottom_cat.  
> **username_25**: As a katz in a hat, I always enjoy cats in a hat.  
> **username_26**: I read this to my intro class when we introduce recursion. It's not a perfect match, but works really well to intro the concept. Plus, high school kids love it when their teacher reads them a Dr. Seuss book.  
> **username_8**: I just rediscovered this answer, and I wish I could upvoted it a second time. It's just so delightful!  
> **username_0**: is there an end state to the cat in the hat?  
> **username_22**: @username_0 I don't have the book in front of me, but the interwebs tell me it's Little Cat Z.  

---

### Answer by username_5 on 2017-05-23. Score: 9

### Recursion as a loop

I'd present recursion as a form of a loop rather than being separate thing. Then, I'd show the students how to covert between flat form and recursive form, and discuss the pro's/con's of using both in implementation.

### Flat-vs.-recursive formats rather than examples of recursion

Since any loop can be written in recursive format, there's basically infinitely many examples that could be presented. But, some seem to make more sense to people in recursive form than others. Why?

This could be a fruitful avenue for class discussion. For example, another answer here gave the example of fractals - why should fractals be seen as more recursive than, say, counting, when both loops can be written in flat form or recursive form just as easily? Then what does this imply - should we just always use one form over the other, or do they each have their place?

I love discussions like this, and I think that they could make the class fun!

### Ideas for coursework (homework/projects):

1. *[intro-level]* Students are given a large number of loops in flat form, then must rewrite them in recursive form.
2. *[intro-level]* Students are given a large number of loops in recursive form, then must rewrite them in flat form.
3. *[college-level]* Short-answer questions about which form they should use in real-life coding scenarios. For example, in some situations flat form's much preferable to avoid stack overflows and implement tail-call optimization when not supported by the underlying platform.
4. *[college/grad-level]* Write an interpreter or meta-programming function that converts between flat and recursive forms.

> **Comments:**
> **username_17**: _"Then, I'd show the students how to covert between flat form and recursive form, and discuss the pro's/con's of using both in implementation."_ Due to the finite stack, if you **can** convert between a loop or recursion, the loop is objectively superior. Recursion is reserved for those cases where loops simply don't cut it (or become insanely complex)  

---

### Answer by username_36 on 2017-05-24. Score: 8

I bought a set of nested Russian dolls (Matryoshka dolls).

1. Show the assembled set - how many dolls are there? We don't know, but maybe there is one inside - take a look
2. Yes, now how many dolls? We don't know, but maybe there is one inside...
3. Repeat until there is not a doll inside - this is the bottom of the stack.
4. Now reassemble the stack, counting the dolls as you go.

> **Comments:**
> **username_17**: "Repeat until" suggests that there is no need for recursion in this example, which there indeed isn't here. Your analogy is perfectly encapsulated by e.g. a linked list, which does not require recursion to traverse.  

---

### Answer by username_37 on 2017-07-01. Score: 8

Although there already is many great answers, one analog I found helpful was the dictionary lookup analogy (this is different than the dictionary binary search analogy). It goes like this:
Lets say you want to know what the word "long" means. You look up the word in dictionary.com find that it means "having considerable linear extent in space." Lets say for the sake of example that you do not know what "linear" and "extent" means. Then you would look up those words definitions. If theres any word in those definitions that you don't know, you would look that up in the dictionary and so on. 
In code, it'll look something like this:
public static void lookupInDictionary(String word){
   String definition = getDefinition(word);
   if(understandsAllWordsIn(definition)){
       return;
   } else {
       for(String word: wordsNotUnderstood(definition)){
           lookupInDictionary(word);
       }
   }
}

You can also use this to teach infinite recursion. Lets say this was the dictionary:

Hello: Hi
Hi: Hello

If one tried to call lookupInDictionary("Hello") or lookupInDictionary("Hi"), it would recurse infinitely.

> **Comments:**
> **username_8**: That's a clever little example.  :)  Welcome to [cseducators.se]. I hope we hear more from you in the future!  
> **username_30**: Good one!  And if you get a stack overflow, it's time to get a simpler dictionary and start over!  

---

### Answer by username_27 on 2017-05-23. Score: 7

One of my favorite examples of recursion is evaluating an arithmetic expression. The downside is that evaluation isn't particularly interesting, but the upside is significant: they've already done it in a programming course! Usually, you'll very early on cover order of operations and expression evaluation in a programming course--but the algorithm we teach them is recursive "find the innermost expression, evaluate it, then move outwards". Here's an example of it in use: <http://courses.cs.washington.edu/courses/cse143/16au/lectures/power-of-recursion/lecture12-recursion.pdf>

> **Comments:**
> **username_16**: "find the innermost expression, evaluate it, then repeat"" is actually a *non-recursive* algorithm for expression evaluation.  
> **username_27**: The "move outwards part" is usually implemented via recursion.  

---

### Answer by username_28 on 2017-06-14. Score: 7

I've used Carl Burch's analogy several times

> Somebody is a Jew if she is Abraham's wife Sarah, or if his or her mother is a Jew.

[He has a nice set of pages at CMU](https://www.cs.cmu.edu/~cburch/survey/recurse/index.html)

> **Comments:**
> **username_8**: That's a really clear example. Nice!  
> **username_29**: I'm Jewish and my daughter just had a bat mitzvah, but her mother is not Jewish. Many if not most Jews don't follow the custom given in this answer. It is a recent custom relative to Torah, which describes many non-Jewish women having Jewish children with a Jew. My daughter wants to be a software engineer and I think this example would make her feel badly. Not to expect political correctness, but I'd avoid this example because it misrepresents Judaism to non-Jews. Then again, the rule is absolutely recognizable to any Jew and anyone like my daughter can let it roll off. Thanks for sharing!  
> **username_28**: I believe Dr Burch says somewhere, he overheard it at a dinner party and it's not a canonical method of determining whether someone is Jewish. Just a neat analogy for recursion.  
> **username_25**: In addition to patrilineal descent (many Reform Jews today, not accepted by Orthodox - and also debatable as to patrilineal vs. matrilineal before the Torah was given to the Jewish people, but I digress) and conversions (which obviously break the algorithm), this leaves open the question of whether Abraham himself was Jewish. As with so many other things in computer science, the edge cases will get you every time!  
> **username_30**: @BennettBrown, I think it's a good analogy, and can be accompanied by a statement that this isn't a *real* definition of Judaism, just a useful analogy for demonstrating recursion.  
> **username_31**: It *is* cute.  But aside from the fact that it's not really correct, as already noted, it really describes a recursive data structure.  Now recursive programs are naturally used to process recursive data structures.  But in my experience, recursive definitions of recursive data structures are even more magical and mysterious to students than recursive functions are.  Of course, once you get the idea you realize how natural and powerful this all becomes.  But for undergraduates, from what I've seen, it's extremely sophisticated.  

---

### Answer by username_15 on 2017-05-23. Score: 7

Rather than use analogy, I think it best to demonstrate the power of recursion on a problem for which the recursive solution is natural and the alternative solutions are an obvious exercise in masochism, to write and especially to prove. Take the Towers of Hanoi problem. When one sees how the problem just cleaves and dissolves into the recursive formulation, that experience of awe will drive one to a deeper and more nuanced exploration of recursion. Elegant expression requires no analogy.


---

### Answer by username_32 on 2017-06-29. Score: 6

I demonstrated this recursion example in class. I draw a large square on the board and ask a student to picture it like a 3x3 grid (like Tic-Tac-Toe). Then the student outlines the center square. Next, the student looks at the other eight squares and repeats the process in each of them. And so on. And so on. That illustrates the process. If you do this in a program, you get the window below. And here's a Java program I wrote to create that window: [Squares.java](https://github.com/CoachEd/JavaExamples/blob/master/Recursion/Squares.java).

[![enter image description here](https://i.sstatic.net/sJLvK.png)](https://i.sstatic.net/sJLvK.png)

> **Comments:**
> **username_30**: Good, but that's not really an *analogy.*  
> **username_0**: is there an end state?  
> **username_12**: A Sierpinski Carpet certainly looks cool and helps explain the concept, but it's unlikely that students are going to be able to code it (or understand code you give them) as their very first recursion project. There are too many recursive calls and computing the locations is likely non-intuitive for a beginner. It might be suitable as part of a graphics-focused CS basics course in Scratch or P5, but even here, it's probably a third or fourth project rather than the first. I remember struggling with a simplified version of this project quite a bit in my second CS course.  
> **username_17**: @username_0: Mathematically, there is no end state. However, you can introduce one computationally, whereby your image generating algorithm stops once the squares are smaller than a pixel and therefore make no visual difference anymore anyway.  

---

### Answer by username_33 on 2017-05-23. Score: 6

Rather than use an analogy, you could give a real world example. The way a tree grows, the shell of a snail, the petals on a sunflower. I believe these are all fine examples - the same solution applied over and over again to a problem until a base case is reached (such as a lack of resources or a height limit at which point water can't be delivered to the leaves)

> **Comments:**
> **username_0**: Hi Marc, I like these, can you expand on how you would use any of these? For example (and rather simply) the tree: for branch, if water available, grow branch, split branch in two.  
> **username_23**: Your examples are missing a purpose. It may seem obvious, but I'm not sure the snail shell example works as well as 'fill a volume of soil with uniform root density'  
> **username_34**: I think students are _surprised_ and _fascinated_ to see the pattern of a recurrent arithmetic sequence emerge in nature (e.g., the Fibonacci sequence in the petals on a sunflower).  I don't think this taps into any deep intuition for them. So, to say "if you want to understand recursion, just reflect on the natural processes around you that have surprising recurrent properties..." may not be helpful.  

---

### Answer by username_35 on 2017-05-23. Score: 5

To make for a hands-on demonstration, I brought in a set of my son's Mega Bloks:

I slowly built up a stack of blocks, and using a dry-erase marker, wrote the calling function and its argument on the block itself. With each new call, I "pushed" the function call onto my stack and then "popped" them off one by one as the functions began to return values rather than more function calls.
I used a basic factorial problem, so my stack of blocks ended up looking something like this:
--factorial(1)--
--factorial(2)--
--factorial(3)--
--factorial(4)--
--   main()   -- 

Students could see how one call to factorial relied on other calls and so on until reaching the base case which "tore down" the stack we had just built.
One of the magical elements of recursion for students is how a function can call itself. The idea of return values and a growing stack of function calls at least gave a tangible and visual example for something that can be abstract and initially challenging to understand.


---

### Answer by username_38 on 2017-06-14. Score: 4

I think a computational joke is in order to help students get started.

All numbers are interesting, for a function $F()$

$F(0)$ is interesting because it's the first number.
$F(F(0))$ i.e. 1 is interesting because it's either interesting or if not interesting is the first non-interesting number and therefore interesting. $$F(F(F(0)))$$ is interesting because...

> **Comments:**
> **username_8**: This looks like [Church Numerals](https://en.wikipedia.org/wiki/Church_encoding) to me. =/  

---

### Answer by username_39 on 2018-01-10. Score: 4

A fairly deep example of a recursive process that has some serious issues that might be discussed with students is as follows.

Suppose that you are a doctoral student in mathematics beginning your dissertation studies. Your advisor has given you a topic to explore, but you know little about it in detail. The advisor suggests a research article as a place to start. The process is:

If the article is by Euclid, read it and you are done.

However, if it isn't by Euclid, then after you read it you will not likely understand everything, so (recursively) read all of the articles in that article's bibliography. However, if you *do* understand everything already, there is no need to pursue the bibliography.

This process (read and chase bib) proceeds until you understand everything you've read or until you reach Euclid.

---

This process is actually closer to the truth than you might expect, but it has at least one (maybe two) serious flaw. After describing the process to students (even relative beginners), ask for their help in identifying the flaw(s). This can lead to a deeper understanding of recursion than a simple (flawless) example.

> **Comments:**
> **username_30**: Interesting starting point for discussion.  It bears mentioning that a much more effective way to *actually* understand an article is to clear up every *word* you encounter that you don't understand, *when* you encounter it, and not go on past a misunderstood word *at all.*  But that's not an example of recursion (just the most important rule of study).  

---

### Answer by username_43 on 2017-10-06. Score: 4

My first practical use of recursion was to work out the total weight of a bunch of containers (portage packs and the various stuff sacks and whatnot inside them.) You know that the blue bag holds the green bag and the tent. You know what the tent weighs. You know that the green bag holds the red bag and the brown bag. Etc.

Similar problems include the "salary burden" of a VP who has several departments under them, and each department has a department head with teams under them, and so on, but without a strict hierarchy so some departments have no teams, just everyone reporting to the head, and some people report directly to the VP but don't head a department, etc. You could also do revenue within a large company the same way. Or inventorying your personal possessions.

> **Comments:**
> **username_7**: Not everything is a tree, but good examples: Trying to organise everything as a tree, such as a company, does not work to produce well functioning organisations. See “a city is not a tree” — Christopher Alexander.  
> **username_43**: I would never argue with the author of one of my favourite books, but the point was that someone else set the company up like that and now you need to make certain calculations on it like "what do we spend on R&D?" and recursion is a way to do that calculation. Since we are just looking for good examples, whether they in fact represent best practices in the real world of running companies isn't super relevant.  

---

### Answer by username_22 on 2018-07-25. Score: 3

This is an old question with lots of answers, but a new one just occurred to me: long division. The benefit here is that most students will already be familiar (and hopefully comfortable) with the mechanics of it, so "recursion" is just another way to talk about something that's already familiar.

> **Comments:**
> **username_40**: Good one!! Never thought about it before.  

---

### Answer by username_22 on 2022-06-07. Score: 3

A new answer for this came to me today. Infinite indirect recursion:

> Pete and Repete are in a tree. Pete falls out. Who's left?


---

### Answer by username_41 on 2017-06-17. Score: 3

Google recursion.

[![enter image description here](https://i.sstatic.net/BIFA7.png)](https://i.sstatic.net/BIFA7.png)

It's a recursive link! Ah, google easter eggs...

Then, you can maybe give them a problem that depends on recursion - like, say, a multiplication algorithm of some sort (I saw one somewhere that used recursion and was pretty simple - I'll edit to add it if I find it) to give a more programming oriented example.


---

### Answer by username_39 on 2017-06-30. Score: 3

I hesitated to answer since most of the answers given are already so good. However, I've also used https://en.wikipedia.org/wiki/There_Was_an_Old_Lady_Who_Swallowed_a_Fly as an introduction, though it isn't precisely recursive. It is more focused on a list as a stack, which leads naturally to recursion. 
In my class we occasionally had "Choir Practice" in which I'd ask a number of students to participate in various "games." For this exercise I'd give each of them a Script card. Starting with only myself and one student, I'd do one verse of the poem, then "push" another student on to the stack and continue. 
I start (with one student) and say:
There was an old woman who swallowed a fly,

I then point to the one student who reads his/her script card. The first says:
I don't know why she swallowed a fly, Perhaps she'll die.(Take a bow.)

Then, "pushing" the second student (now I have a stack of two), I'd say:
There was an old woman who swallowed a spider, That wriggled and jiggled and tickled inside her,

I'd point to the (new) stack top who would read the script:
She swallowed the spider to catch the fly, (point to the next person)

etc for as long as you like. "Pointing" to a person is passing them the message to read (sing-act) their own script. 
Depending on how you talk about the exercise you can use it to reinforce lists, stacks and/or recursion. Note the base case (...take a bow). The "message" sent is recursive, though. You can also explore what happens without a base case in your follow up discussion. 
A bit foolish, but my University students tended to like it even if they did roll their eyes a bit. 
Note that such "active learning" exercises always require follow up discussion in which you point to the mapping between the elements of the game and the lesson to be learned and students get to unwind any puzzlement. 

Here is a link to the card deck


---

### Answer by username_42 on 2018-01-10. Score: 3

When I was first taught recursion in a high school CS class, the teacher had us read a short story called **Martin and the Dragon**, found in chapter 8 of "Common LISP: A Gentle Introduction to Symbolic Computation" by David S. Touretsky. In the story, a boy named Martin visits an unruly dragon and uses recursive techniques to coerce it into helping him with a few different computational tasks that are common in LISP, including iterating over a list, calculating a factorial, counting, and calculating fibonacci numbers (which also teaches infinite recursion).

A shorter analogy might be a multi-level marketing scheme - it starts with one person, who has to recruit several more, who each in turn have to convert a few others, and so on.

Genealogical lines are also a naturally recursive data structure - you have two biological parents, who in turn each have two biological parents, and so on and so forth. It can also work for children and/or other species.

> **Comments:**
> **username_39**: Welcome to CSEducators. We hope you come back often. Could you expand your first paragraph a bit to give at least a hint about _which_ recursive techniques.  

---

### Answer by username_24 on 2017-06-29. Score: 2

Came across this one. I simply loved it:

> [Hofstadter's Law](https://en.wikipedia.org/wiki/Hofstadter%27s_law): It always takes longer than you expect, even when you take into account Hofstadter's Law.

This is especially good when explaining debugging a recursive method, or the call stack. When you reach the end of the sentence, you go to the definition of Hofstadter's Law (If you are a compiler). And this goes on and on (essentially a stack overflow).


---

### Answer by username_44 on 2022-02-14. Score: 2

You're working in an office. If a question comes up, the first person you consult is yourself. If the person to consult doesn't know the answer, they consult their manager, and upon receiving the answer pass it down the hierarchy again. Recurse until you have the answer.
So:
ask( person from, person to ):
  if not: from knows the answer
     ask( from's manager, from )
  tell( from, to )

and invoke this with
ask(me,me)

(You still have to define tell(from,to) and make sure that's a no-op if from==to.)
I like this example because it is not trivially iteratable as tail recursion. This explicitly goes up and down the stack.
Next step: if you ask something of someone, you take out a notepad to record what they tell you. If that person doesn't know, they take out a notepad and ask further. Now you know where stack overflow comes from: there is a bunch of notepads open simultaneously, and they all take up some amount of memory.

> **Comments:**
> **username_45**: The image of each person taking out a notepad just reminds me of Dr Seuss somehow. He had some things that were self-referential in his stories, I think. Very visual and memorable.  
> **username_44**: Like https://2.bp.blogspot.com/-G5cMV3yjXCU/VOyZkzIYGlI/AAAAAAAAHMc/yJmT_WHduqs/s1600/51kRVqJxa3L.jpg ?  
> **username_45**: "Oh, no you don't, Mr Feynman! It's turtles all the way down." I had some of those books as a child. Others I saw at the pediatrician's office. Yes. Pretty brilliant. We need more teaching like that. And Mr Rogers...  

---

### Answer by username_40 on 2018-07-26. Score: 1

Pretty late to see this. Thought to add my two cents as well.

Recursion simply reminds me of the barber shop (provided he has parallel mirrors on either side of you) where we used to observe the array of mirrors (*Fun Fact: once even counted them uptil 83 until they were no more visible*). Also, during matches, when often cameraman used to pan at the giant-screen and we used to see the array of screens in it (all recursively).

> **Comments:**
> **username_8**: Recursion with no base case!  :)  
> **username_40**: Haha point. Can we count the skewness of reflection angle or minimum size as base case? Just a thought came to my mind in reply to your golden point.  

---

### Answer by username_46 on 2018-05-05. Score: 1

I think there are two separate aspects to understanding recursion:

How to use recursion to solve problems
How recursion is evaluated

How to use recursion
Let's look at an example: maximum depth of a binary tree (where a tree with a single node is depth 1). A recursive solution in python might look like this:
def max_depth(root):
  if root is None:
    return 0

  return 1 + max(max_depth(root.left), max_depth(root.right))

You don't need to think about how this is actually evaluated; you just define it how you would mathematically. If I somehow know that the maximum depth of the left branch is $x$ and the maximum depth of the right branch is $y$ and that $x > y$ (without loss of generality), then I know that the maximum depth of the entire tree is $1 + x$. This way of thinking about problems is one way you can use recursion.
Of course, you need to make sure that the inputs to the recursive calls are in some way smaller than the input to the function that makes the recursive call, which segues into how recursion is evaluated.
How recursion is evaluated
To think about how recursion is evaluated, we can use the same example. In the example above, there are pending recursive calls, waiting to return (note that recursion does not necessarily have this, see tail call). To see this, suppose our tree looks like this
    O <- root
   / \
  O   O
 / \
O   O

and you have a variable r storing the root. If you call max_depth(r), it will try to evaluate the else clause; it will evaluate max(max_depth(r.left), ...) and then add 1 to that result. To the r.left recursive call, the input looks like this
     O
    / \
   O   O

And for the r.right recursive call, it is simply this:
O

The r.left recursive call evaluates else clause, which means it tries to evaluate the max depth of the left and right subtrees, and add 1 to whichever is greater.
The r.right recursive call also evaluates the else clause.
So at this point you think of the return value of the original call to max_depth looking like this:
return 1 + max(
               1 + max(max_depth(root.left.left), max_depth(root.left.right),
               1 + max(max_depth(root.right.left), max_depth(root.right.right))
              )

Both recursive calls of the left branch have trees that look like this now
O

while both recursive calls of the right branch, since it was just a node without any children, have trees that are empty, which is None in Python. Thus, they fall to the base-case, which means it is evaluated as 0.
So now the original return value is like this
return 1 + max(
               1 + max(
                       1 + max(max_depth(root.left.left.left), max_depth(root.left.left.right)),
                       1 + max(max_depth(root.left.right.left), max_depth(root.left.right.right))
                      ),
               1 + max(
                       0,
                       0
                      )
              )

All recursive paths from the right branch already reached the base-case, and now on this recursive call, all children of the left branch will as well, which means the return value of the original function is now
return 1 + max(
               1 + max(
                       1 + max(
                               0,
                               0
                              ),
                       1 + max(
                               0,
                               0)
                      ),
               1 + max(
                       0,
                       0
                      )
              )

which evaluates to
return 1 + max(
               1 + max(
                       1 + 0,
                       1 + 0
                      ),
               1 + 0
              )

and
return 1 + max(
               1 + 1,
               1 + 0
              )

and
return 1 + 2

finally
3

Note, this evaluation was not performed according to any formal evaluation model (see substitution model or environment model); it was merely to help build intuition for how evaluation could be done.
Extra (tail-recursion): I mentioned earlier about how recursion does not necessarily have these pending function calls that must be recursed back to once they finally have the result of the recursive call. Consider a recursive function to find the sum of a list (ignoring the python built-in sum()):
def sum_list(lst):
  if lst == []:
    return 0

  return lst[0] + sum_list(lst[1:])

This indeed would have pending recursive calls, as it waits to add lst[0] to the result of the recursive calls. We can make this tail-recursive by accumulating the sum of the list in an argument that is simply returned unmodified at the end:
def sum_list_tail_recursive(lst, result):
  if lst == []:
    return result

  return sum_list_tail_recursive(lst[1:], result + lst[0])

Once this evaluation reaches the base-case, it has the the result of the original call to sum_list(), and it does not need to be added to, or modified in any way as you recurse back up, and so if a compiler/interpreter recognizes this, it can optimize by skipping directly to the first call, eliminating the need to recurse back to it step-by-step.


---

### Answer by username_47 on 2021-09-11. Score: 1

Here is my cake-baking analogy:

Suppose the recipe for a 3-layer cake said "first bake a 2 layer cake, then add flour, sugar, and butter, and put it in the oven".

And the recipe for the 2-layer cake says "first bake a 1 layer cake, then add flour, sugar, and butter, and put it in the oven".

But once you get to the 1-layer cake, that's it. You've reached the base case. The buck stops there. Unlike the recipes for the 2-or-more-layers cakes, the recipe for the 1-layer cake doesn't refer to any other recipes.

I think this analogy captures the concept of the base case (the 1-layer cake) and the recursive step (add sugar, flour, and butter then bake).


---

### Answer by username_48 on 2018-05-04. Score: 1

You can do some stuff with the filesystem  
like. start with a folder and count all files in it  
or let them create a overview of folders and files


---

### Answer by username_51 on 2018-05-04. Score: 1

I thought of repetitive song lyrics, initially the [Song That Never Ends](https://www.youtube.com/watch?v=0U2zJOryHKQ) - a good example of infinite recursion. Then came to mind [Ten Green Bottles](https://www.youtube.com/watch?v=T0ooQv7oHvw), which I think is a nice simple illustration with a clear base case and inputs that keep reducing, ultimately to the base case.


---

### Answer by username_49 on 2018-09-07. Score: 0

I came up with an analogy that helped me visualize recursive programming a great deal.

1. Imagine a water tank with an inflow pipe on one side. On the other side, about halfway up the tank, is the outflow pipe which is where you collect the water.
2. Water enters the inflow pipe. As it enters, it gets tested to see if it's clean. If it's found to be clean, a valve will empty the water directly into the tank and let the clean water flow into the tank and then right through to the outflow pipe and we are done.
3. But if the water test reveals that it is dirty, it gets decontaminated by some amount then gets directed into another tank inside of bigger tank.
4. This second tank does exactly the same thing as the outer tank. It first tests the water, dumps it into the tank if it is clean and if it isn't, it cleans it a little bit, and then sends it to a third inner tank. This process continues.
5. When the last inner tank is reached and the water is completely clean, the valve lets the water spill directly into the tank. This water then flows out of the tank though the outflow and into the outer tank surrounding it. That outer tank fills up until water spills out into *its* outer tank. Each of these tanks can also treat the water if they want (add chlorine or fluoride to it or even send it to another recursive processing tank).
6. This cascading action continues until the last outer tank spills out the clean, processed water, representing the data we desire.

> **Comments:**
> **username_7**: This seems like an overly complex way to clean water.  
> **username_8**: @username_7 Actually, except for the placement of the tanks, this is not far off from the real process. Water is treated in one tank, then another, then another, and so forth until it is clean. At least in NYC, the last "tank" is really an ecosystem. It is a biocleaning using algae, and many animals eat the algae, many animals eat those animals, and so forth. On the radio, they said it is actually quite beautiful in there.  

---

### Answer by username_50 on 2017-09-22. Score: -1

Maybe you can start by showing a clip of *Groundhog Day*. Explain how his days are constantly in the same loop, and the loop does not end until he "fixes" something.

Which in programming would be considered a `base case`.

> **Comments:**
> **username_39**: Seems a bit weak, actually. Where is the recursive "call"? Might be better for `while loops` where you also need a stopping condition.  

---

