Tag Info

101

I find a very easy to understand example for recursion is the folder structure on a computer. Look through all folders (within a certain location) and... list all .doc files, for example. First, you look in the location you were given and see what you're looking for... or not, but you see more folders. Then you take each of those folders, look into them and ...

26

One good example is to make permutations of all of the letters in a word of arbitrary length. It's quite tricky to do iteratively, since you essentially have to recreate the program stack to get it done. The recursive solution, however, is clean and clear. Let the students try to work in pairs on an iterative solution for just five minutes. The goal ...

22

The Tower of Hanoi was one of the first ways that I encountered recursion. "The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: Only one disk can be moved at a time. 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 ...

21

Writing recursive code to output the Snowflake Curve (Koch snowflake) was something that definitely pushed my buttons early on. It's formed as follows: The Koch snowflake can be constructed by starting with an equilateral triangle, then recursively altering each line segment as follows: divide the line segment into three segments of equal length. draw an ...

19

Other than the obvious merge sort, I really like the minimax algorithm, especially when applied to creating a computer player of a simple game. Start with something simple like tic-tac-toe. When it's your turn, you can think about putting an X on each of the 9 squares. Then you have to think about what your opponent would do in each case. Your opponent ...

18

Quite honestly, I would be upfront with them about the debate. Send them to a couple other SE threads: Efficiency: recursion vs loop “Necessary” Uses of Recursion in Imperative Languages Are functional languages better at recursion? This now becomes a teachable moment on a number of levels: imperative v. functional languages, recursion v. iteration, "...

18

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

15

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

14

When I teach recursion, even if I am not at a point in the curriculum where it is possible to introduce trees in coding problems, I always at least provide a high level discussion of trees, and the way that recursion is a natural way to process anything organized in a tree. Anyone that has worked with files and folders/directories on a computer is already ...

14

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

13

I'm going to focus on student's understanding recursion at a fairly deep level, rather than coding. First, to really understand recursion you need a sense of its parts. There is the base case, of course and most teachers spend time working on that, but students often miss it. But Before the process hits the base case there is a winding phase working toward ...

8

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

8

Operating on the key word, motivate, I do believe that Andrew T. had the best choice with Tower of Hanoi. Yes, it's an old one, and it does not lead to anything useful once it's done, (the code is not reusable for some other "real world" problem.) Yet it remains a classic for some reason. I'm going to speculate that the reason is that when ...

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

7

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

7

I bought a set of nested Russian dolls (Matryoshka dolls). Show the assembled set - how many dolls are there? We don't know, but maybe there is one inside - take a look Yes, now how many dolls? We don't know, but maybe there is one inside... Repeat until there is not a doll inside - this is the bottom of the stack. Now reassemble the stack, counting the ...

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

7

Tree Traversal Let's compare the recursive and iterative approaches to doing an in-order traversal of a binary search tree. Recursive approach void orderedTraversal(const Node *node, void (*f)(int)) { if (!node) return; orderedTraversal(node->left, f); f(node->val); orderedTraversal(node->right, f); } Iterative approach typedef ...

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

6

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

5

Several answers have said things like "We need recursion to handle tree structures." The problem with this type of answer is that the student then asks "Why would we have a tree structure in the first place?" @Syndic's example of handling directories with subdirectories is probably the best answer, but there are others. My favorite example where recursion ...

4

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

4

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

4

In addition to the other good answers already provided, I want to add that students should learn recursion because they will encounter it in real life. Any one of them who goes on to program for a living will at some point need to understand, maintain, or debug a recursive function. So they must be able to recognize recursion, understand how it works, ...

4

Having a discussion about the plusses and minuses can be valuable, but sometimes what you need is a motivating example. It's true that loops and recursion are equivalent in the sense that they can provably accomplish the same tasks. However, some problems are simply astoundingly easier with recursion, such as iterating through a tree, or finding all of the ...

4

For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion. So you can implement while True: recursively. In these languages recursion is used more. In python it is used less, unless the depth is (as you said) O(log n). However the design may be easier done using recursion, and you can always convert recursion ...

4

An introductory programming class is a good place to familiarize students with some real-world issues in programming apart from the more popular ones. Using recursion is just one example of how they might address them. Programming for the long haul (whether it's for production or to support one's own research, for example) is not always about obtaining the ...

4

Often times, google is our best of friends (I hope). A rather simple search leads to a very informative site: http://introcs.cs.princeton.edu/java/23recursion/ It is very thorough, and explains many use-cases for recursion. Another very handy resource is, inevitably, Stack Overflow: this question also provides some information, but it is rather specific....

4

For learning recursion... A student with some programming experience might just need a brief tutorial. Since I teach CS50 AP, I make use of CS50 Study which has a page dedicated to recursion here. There is a slideshow with speaker notes as an overview, tips and tricks for using recursion, and sample problems with solutions. The language in question is C, ...

4

No This may be a good way to test understanding of function calls, and the stack. However I don't think it helps much with recursion. As when we design we need to abstract. To do this we need to be able to think without having to keep all of the detail in our heads. We need to focus only on externally visible behaviour, not internal details. Yes Having ...

Only top voted, non community-wiki answers of a minimum length are eligible