36
$\begingroup$

When teaching recursion, what is the best analogy people use to teach the idea of recursion. There are some nice artistic representations

enter image description here

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.

$\endgroup$
  • 7
    $\begingroup$ This is language agnostic, I'm really looking forward to ways for students to grasp the concept of recusion $\endgroup$ – pluke May 23 '17 at 15:03
  • 7
    $\begingroup$ Wait, what's recursion again? Okay, Google "recursion"... huh, it gives "Did you mean: recursion"? Okay, clicking that... huh, it gives "Did you mean: recursion"? Okay, clicking that... huh, it gives "Did you mean: recursion"? Okay, clicking that... huh, it gives "Did you mean: recursion"? Opps, out of characters - stack overflow! $\endgroup$ – Nat May 23 '17 at 15:27
  • 4
    $\begingroup$ You may find this discussion helpful. $\endgroup$ – Miles May 23 '17 at 20:25
  • 2
    $\begingroup$ There is a question about recursion here cseducators.stackexchange.com/questions/17/… $\endgroup$ – ctrl-alt-delor May 28 '17 at 16:17
  • 1
    $\begingroup$ curse = to abuse something verbally. recurse = to repeat oneself while abuse something verbally $\endgroup$ – pojo-guy Jul 3 '17 at 23:43

28 Answers 28

15
$\begingroup$

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;
}
$\endgroup$
  • 8
    $\begingroup$ 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? } $\endgroup$ – Andrew Sundstrom May 23 '17 at 21:08
  • $\begingroup$ The first one is just a loop... $\endgroup$ – immibis Jan 11 '18 at 2:17
21
$\begingroup$

The Tower of Hanoi was one of the first ways that I encountered recursion.

Tower of Hanoi, cc by-sa Bin im Garten

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

$\endgroup$
16
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Nice, with a cute ending :) $\endgroup$ – Ben I. Jun 18 '17 at 18:32
  • $\begingroup$ Glad it's a computer scientist and not an anthropologist. Otherwise the hex conversion would be cause for using a counter-curse. $\endgroup$ – Gypsy Spellweaver Jul 28 '18 at 23:36
13
$\begingroup$

The image that I kept in my head when I was learning recursion was from Dr. Seuss: enter image description here

$\endgroup$
  • 4
    $\begingroup$ @richard no. they don't need to. otherwise you get stackoverflow. $\endgroup$ – ItamarG3 Jun 18 '17 at 18:08
  • 1
    $\begingroup$ As a katz in a hat, I always enjoy cats in a hat. $\endgroup$ – manassehkatz Aug 8 '17 at 4:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Nutt Sep 23 '17 at 14:04
  • 1
    $\begingroup$ I just rediscovered this answer, and I wish I could upvoted it a second time. It's just so delightful! $\endgroup$ – Ben I. Apr 7 at 15:41
  • 1
    $\begingroup$ @pluke I don't have the book in front of me, but the interwebs tell me it's Little Cat Z. $\endgroup$ – G. Ann - SonarSource Team Jun 11 at 12:13
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "find the innermost expression, evaluate it, then repeat"" is actually a non-recursive algorithm for expression evaluation. $\endgroup$ – immibis Oct 5 '17 at 23:20
  • $\begingroup$ The "move outwards part" is usually implemented via recursion. $\endgroup$ – adamblan Oct 7 '17 at 0:16
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ That's a really clear example. Nice! $\endgroup$ – Ben I. Jun 14 '17 at 17:02
  • 5
    $\begingroup$ 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! $\endgroup$ – Bennett Brown Jun 15 '17 at 7:30
  • 4
    $\begingroup$ 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. $\endgroup$ – JPearse Jun 15 '17 at 19:42
  • 2
    $\begingroup$ 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! $\endgroup$ – manassehkatz Aug 8 '17 at 4:16
  • $\begingroup$ @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. $\endgroup$ – Wildcard Jan 13 '18 at 7:15
6
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – pluke May 23 '17 at 15:15
  • 3
    $\begingroup$ 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' $\endgroup$ – Sean Houlihane May 23 '17 at 17:02
  • $\begingroup$ 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. $\endgroup$ – GermaneDork Jun 8 '17 at 4:50
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a clever little example. :) Welcome to Computer Science Educators. I hope we hear more from you in the future! $\endgroup$ – Ben I. Jul 1 '17 at 18:40
  • $\begingroup$ Good one! And if you get a stack overflow, it's time to get a simpler dictionary and start over! $\endgroup$ – Wildcard Jan 13 '18 at 7:18
4
$\begingroup$

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

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.

$\endgroup$
4
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ Good, but that's not really an analogy. $\endgroup$ – Wildcard Jan 13 '18 at 7:17
  • $\begingroup$ is there an end state? $\endgroup$ – pluke Jun 10 at 21:26
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Wildcard Jan 13 '18 at 7:22
2
$\begingroup$

Google recursion.

enter image description here

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ctrl-alt-delor Oct 6 '17 at 12:34
  • $\begingroup$ 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. $\endgroup$ – Kate Gregory Oct 6 '17 at 13:24
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Buffy Jan 10 '18 at 11:37
2
$\begingroup$

Came across this one. I simply loved it:

Hofstadter's 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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good one!! Never thought about it before. $\endgroup$ – Failed Scientist Jul 26 '18 at 17:53
1
$\begingroup$

L-system trees are a fun, clear, simple way to show recursion.

e.g.: http://www.malsys.cz/Gallery/GetThumbnail/JFI1IzqW/IqdVGQ

I've taught this in beginner-level Python lessons, and it only requires a few lines of code to build complete trees. Most students love the artistic outcome - especially that so little code produced so much graphics.

$\endgroup$
  • 1
    $\begingroup$ the link is dead? $\endgroup$ – pluke May 23 '17 at 19:59
  • $\begingroup$ Site seems to have gone offline :(. Google "l-system trees" and you'll get many great examples in image-search. $\endgroup$ – user31 May 24 '17 at 1:44
  • $\begingroup$ Perhaps you want to replace the link @Adam with one that's still online? :) $\endgroup$ – G. Ann - SonarSource Team May 29 '17 at 20:27
1
$\begingroup$

I thought of repetitive song lyrics, initially the Song That Never Ends - a good example of infinite recursion. Then came to mind Ten Green Bottles, which I think is a nice simple illustration with a clear base case and inputs that keep reducing, ultimately to the base case.

$\endgroup$
1
$\begingroup$

I think there are two separate aspects to understanding recursion:

  1. How to use recursion to solve problems
  2. 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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Recursion with no base case! :) $\endgroup$ – Ben I. Jul 27 '18 at 0:26
  • $\begingroup$ 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. $\endgroup$ – Failed Scientist Jul 27 '18 at 4:34
0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ This seems like an overly complex way to clean water. $\endgroup$ – ctrl-alt-delor Sep 8 '18 at 11:16
  • $\begingroup$ @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. $\endgroup$ – Ben I. Sep 13 '18 at 2:15
-1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Seems a bit weak, actually. Where is the recursive "call"? Might be better for while loops where you also need a stopping condition. $\endgroup$ – Buffy Sep 22 '17 at 20:00
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.