|
What examples to teach recursion with?
Besides the old standby's factorial, fibonacci, and power(x,k) can you think of other simple examples to teach someone how recursion works?
Thanks
Bella
Tuesday, May 18, 2004
http://discuss.fogcreek.com/joelonsoftware/
Edward
Tuesday, May 18, 2004
LOL!
Philo
Tuesday, May 18, 2004
The really basic recursion examples like factorial always bothered me because it's so easy to imagine how to accomplish it iteratively that some students end up perceiving recursion as a pointless academic exercise rather than an important tool.
A few other ideas:
Binary trees, though that tends to assume a level of comfort with pointers.
Quicksort. Probably too much noise related to the algorithm itself rather than the recursive aspects, though.
Or: What about traversing a filesystem hierarchy, looking for a file in an unknown subdirectory? Anyone who's writing code is certainly familiar with the nesting of directories in a filesystem, traversing it doesn't require a big diversion into data structures, and it's *useful*.
John C.
Tuesday, May 18, 2004
>>What about traversing a filesystem hierarchy
Yup...that is a excellent example..and one I was going to suggest. There is not such a easy way to code such a solution manually…and, yet it is not too hard to understand what needs to be done…
The tree with pointers is cool..but is usually tough beginners to grasp…
Albert D. Kallal
Edmonton, Alberta Canada
Kallal@msn.com
Albert D. Kallal
Wednesday, May 19, 2004
Another example would be an organizational hierarchy - start with the CEO/University President and work down through [x] levels of organization where x=1..n
Philo
Philo
Wednesday, May 19, 2004
Hmmm....
I like the famous 'Towers of Hanoi' problem as a good recursion example. Other could be, reverse printing a linked list and yes, how about 'Knight's tour on a chessboard'.
The Knights one is tough though... but maybe start with something like only 4*4 chessboard :)
The One You Loved (TOYL)
Wednesday, May 19, 2004
+1 for binary trees
Dennis Atkins
Wednesday, May 19, 2004
I always liked the pocket telescope (i.e., expandable telescope) analogy. The simple visual image helped me understand recursion immediately.
Also, I've known programmers who've written recursive functions but didn't understand the 3 basics of recursion - base case, general case, and proof that a base case will be reached. I'd emphasize the importance of identifying and commenting these in the code.
yet another anon
Wednesday, May 19, 2004
A rough example might be about cleaning a room. The function clean(room) would see that the room is a composite object, so it would do:
clean(window)
clean(lamp)
clean(lampshade)
clean(lamp-body)
clean(table)
clean(candleholder)
clean(tablecloth)
The lamp and table are composite objects too, so I recursively clean its parts. In other words, my clean() procedure is so useful that I can use it over and over again mindlessly.
The way I code recursively is that if I'm given a Thing, I should be able to handle whatever I get. That way I'm confident I can call the procedure again recursively, and it'll handle whatever I throw at it sanely. In the clean() example above, I might use OOP and call lamp.clean(), which can call lampshade.clean() and lamp-body.clean().
Iteration and recursion both have their strong points, so I use them both in lisp. Recursion is useful when:
- Flipping a switch to make a function cache its params is really sweet.
- I want to redefine a function and have it "take" immediately. Like when I make an infinite loop whose behavior I want to change.
- When I know that a stack-busting recursion must be an error, I can turn off tail-call optimization and have it signal an error to me. (Intentionally brittle software that breaks in testing.)
- I can turn on "trace" which prints out the function's params and return val whenever it's called.
Tayssir John Gabbour
Wednesday, May 19, 2004
+1 for directory trees. Assuming the language has reasonable support for interacting with the filesystem, it's not too onerous. It was also the first recursive task I ever encountered. (Now that I'm going for my BSCS, I just ran across the classic fibonacci... which was utterly ridiculous because iterative is so clearly the way to go for that task.)
Any tree-like structure (like a DOM document) lends itself to recursive programming, but the filesystem is (or should be) familiar to students.
Sam Livingston-Gray
Wednesday, May 19, 2004
Towers of Hanoi is a good problem where recursion is the solution, but it's not an intuitive way to teach what recursion means, IMHO.
Philo
Philo
Wednesday, May 19, 2004
Actually, a file system search is the only place my Java code base performs multi recursive calls, though there are a few places where a method ends up call itself once. Recursion generally isn't the simplest approach.
You could deal with a simple expression evaluator, but it would probably be too complicated, even with addition and subtraction of single-digits numbers.
(5-2)-(4-3) = ?
Julian
Wednesday, May 19, 2004
I learnt recurssion using the towers of hanoi.
I remember being so scared of recurssion, with an 'avoid at all costs' approach. But one I understood it, I loved it.
As a teaching aid I think pictures can be great.
C++ distilled, by Ira Pohl. has a recursive picture on the cover.
A man is in the picture, the man is a copy of the book....
Aussie Chick
Wednesday, May 19, 2004
"My grandmother, who lived to be 97, explained it this way, 'The way to understand recursion is to understand recursion.'"
-- Unknown author of a JavaScript tutorial
offMyMeds
Wednesday, May 19, 2004
I first grasped recursion when trying to write a flood-fill function for graphics. It looked something like this (pseudo-python syntax):
def Paint( x, y, c ):
if PixelColor( x, y ) == c:
return
SetPixel( x, y, c )
Paint( x - 1, y, c )
Paint( x + 1, y, c )
Paint( x, y - 1, c )
Paint( x, y + 1, c )
Unfortunately, this simplistic implementation tends to blow the stack very quickly on a 1024x768x32 graphics card.
Chris Tavares
Wednesday, May 19, 2004
Populate a TreeView control on a form using recursion. That way they can 'see' how it works...
GiorgioG
Wednesday, May 19, 2004
traversing a labyrinth
That is another form of tree/graph walking, just that you can paint a less abstract picture.
Michael Moser
Wednesday, May 19, 2004
To understand recursion, yo have to understand recursion..
Sorry, could not restrain myself ;-)
Really old nerdy joke (translated from swedish).
Yablan
Wednesday, May 19, 2004
Hey offMyMeds,
that's not the way to understand recursion, that's the way to understand catch 22...
The way to understand recursion is to understand all of it's components.
Martin A. Bøgelund
Wednesday, May 19, 2004
Actually, my favorite metaphor for introducing recursion is that it's all about being Lazy:
1. Realize that a task is too big for "you" (the anthropomorphized subroutine) to do alone
2. Identify the smallest possible task, ideally one that's so small that no work at all needs to be done (== base case)
3. Think about how to take a task that's larger than that smallest possible task, simplify it just a bit or split it into pieces, and then give it away to someone else to do. Of course that someone else just happens to be "you", the same sub, once again (== recursive case)
Of course there's that nasty part about being sure you reach the base case, but a stack overflow will usually tell you pretty quickly if you're way off base :-)
John C.
Wednesday, May 19, 2004
I don't think the definition of recursion requires you to have a base case. IIRC it only requires the recursive function to call itself, and I don't see why recursion shouldn't run indefinately.
Martin A. Bøgelund
Wednesday, May 19, 2004
Someone mentioned the knight's tour chessboard problem.
I like the 8-queens problem - place 8 queens on a chessboard so that none of them threaten each other (there are no queens on the same rank, file or diagonal, for those who don't play).
SteveM
Wednesday, May 19, 2004
Also vote for traversing the filesystem. It's a nice 'physical' example: obvious practical applications (always a good motivator to learn something new); results are easily observable; and directory trees are concrete, visible structures requiring no extra introduction. e.g. Maybe write scripts that open every file, or print a tab-indented list of folder names?
has
Wednesday, May 19, 2004
For a good solid real world problem you can't beat the file system.
I think the simplist is to calculate the size of all files in a directory (including sub-directories).
It also gives plenty of scope for investigating alternative methods.
Ged Byrne
Wednesday, May 19, 2004
Just about anything in Haskell.
KayJay
Wednesday, May 19, 2004
Don't forget the joys of depth first, bredth first, reverse order etc. I'm dead jealous, and wish I was learning about recursion again. I love it, its so neat.
About the whole base case thing, and the recursion going on forever, I used to teach it as: "guarded recursion", at some point you want to stop, or cannot go any further.
Divide and Conquer sorting is a great lead into recursion from crappy bubble sort. Plus, you sneek recursion in as a sorting topic. Bring in a deck of shuffled cards and distribute chunks around the class and do a divide and conquer sort 'before their eyes', then pseudo code it.
Have someone pick a card, get all the above ones, hand it to their mate, and the lower ones, hand them to a mate, and repeat. Then hand them back an assemble the deck. Of course you might not want to use all 52 cards!!
Tim H
Wednesday, May 19, 2004
All this recursion talked reminds me of a little Internet bubble problem I encountered....
A pretty smart colleague of mine had left his engineering career to become a programmer. He knew he would be a good programmer, because he was pretty good at Excel macros. It was the bubble, companies were desperate for programmers, so naturally he found a job.
He came to me for assistance with a programming problem one day, and I suggested he use recursion to solve it. "Huh? What's recursion?" Oh God, why do I have to work with programmers without an education.
Herr Herr
Wednesday, May 19, 2004
"To understand recursion, yo have to understand recursion.."
Not really. To understand recursion, you just have to understand recursion - 1.
NoName
Wednesday, May 19, 2004
Just try to visualize a snake eating it's own tail, until it gets nauseous.
int Me() { Me(); }
Wednesday, May 19, 2004
If they've done any mathematics, try drawing an analogy with proof by induction, and the mathematical notion of recursion. The connection between recursion and induction is quite important I'd say. A lot of things in mathematics are (or can be) defined recursively, and then induction used to prove they have desired properties. All sorts of combinatorial functions and identities for examples, or even something simple like defining addition and multiplication recursively for a Peano system and proving things like associativity and commutativity inductively...
Programming wise I'd say it depends a lot if you're teaching a functional language, or if you're teaching more standard 'intended to be useful' java type programming. For the latter I'd try and stress what recursion is actually useful for in that context, ie things which can't (easily) be done iteratively like traversing trees. But in a general with a functional language there are loads and loads of good examples. Definately helps to stress that while functional programs using recursion for simple things tend to 'look' horribly inefficient and silly to those used to C, optimisations on tail-call recursion tend to mean they run as fast as the iterative solution. I thought functional programming was a bit of a joke until someone pointed that out.
Only problems I can remember actually using recursion for in a practical context right now would be:
- traversing file system directory trees
- generating HTML for threaded discussion boards
- Writing code that plays simple board games
- Naive implementation of a web spider
Matt
Wednesday, May 19, 2004
fractals
Yo
Wednesday, May 19, 2004
Recursive routines tend not to run for ever (or rather its a bug if they do) because for practical purposes its a finite universe.
A reasonable example of using recursion to solve a problem is any kind of mapping or movement calculation between points. it might be towns and roads, or squares and counters with orthoganal moves.
Simon Lucy
Wednesday, May 19, 2004
This tutor is fun:
http://www.psychologie.uni-trier.de:8000/projects/ELM/elmart.html
Rikard Linde
Wednesday, May 19, 2004
Given an array of objects, where the array has arbitrary length, write a program that prints all possible subsets of the array (ignoring the sequence of objects within each subset). For example, given an input array like {a,b,c}, the output should look like:
a
b
c
ab
ac
bc
abc
(Recursion is one of the ways in which a solution to this can be implemented).
Christopher Wells
Wednesday, May 19, 2004
Oh yes, and fractals! good point.
Have them plot one of those sierpinski snowflakes! or even better a peano curve :)
Matt
Wednesday, May 19, 2004
I second the motion that fib(), fact(), etc, NOT be taught as examples of recursion. A good interview question is to ask why recursive fib() is a terrible solution to the problem. (Hint: what's it's running time compared to the iterative version?)
If you're looking for an easy-to-explain yet somewhat "meaty" problem that uses recursion, I like topological sorting. And if you explain it in a language with references but not pointers, you don't have to explain pointers first. It has a clear base case and a simple recursive case, but it solves a nontrivial problem.
I wrote an article a while back on implementing a recursive topological sort in JScript, which is here:
http://blogs.msdn.com/ericlippert/archive/2004/03/16/90851.aspx
Here's another approach. You might consider approaching recursive programming as a natural way to solve problems on recursively defined data structures.
When you define a list as "any number of items where one comes after the other", you naturally think of iterative operations on lists -- you want to operate on that list with a "for" loop.
But when you define a list as "either empty, or an item followed by a list" then suddenly it becomes very natural to think recursively. The operation on the list becomes "solve the empty case, or solve the one-item case and recurse on the tail."
Eric Lippert
Wednesday, May 19, 2004
"Tower of Hanoi" isn't too bad, but I have two problems with it. The first is that it is incredibly contrived. The second, is that there is an easy iterative solution that no one ever talks about.
Number the disks 1 to n starting from the top. Never move an odd onto an odd, never move even onto even, never move a larger onto a smaller, never undo the move you just made and never move a disk on an empty spindle unless you have to. Keep moving disks until you're done. No recursion required.
Eric Lippert
Wednesday, May 19, 2004
I remember learning recursion in a high school programming class then using it to solve some sort of maze problem. Funny thing was that while I understood recursion (I think) having learned all the basic examples listed in the original post, it still seems somewhat magical to me. I solved the maze problem on paper for a test, and even getting it backed marked correct, I wouldn't believe it would actually work, untill I coded it and run it.
Une Ternal
Wednesday, May 19, 2004
Une Ternal,
the same thing happened to me. But in reality, that was my friend who had coded the algorithm, while I kept telling him that it wouldn't work...
Pakter
Wednesday, May 19, 2004
Eric
There's an even easier iterative solution to the Towers of Hanoi:
Repeat
1 Move the smallest disc clockwise
2 Make the only possible move not involving the smallest disc
Until you're done
as
Wednesday, May 19, 2004
What about some XML parsing exercise?
MilesArcher
Wednesday, May 19, 2004
Eric - the problem is contrived, or the solution is?
Philo
Philo
Wednesday, May 19, 2004
The problem is for chrissakes! Just take the whole friggin stack and plop it on the destination. Then go enjoy a favorite snack while thinking about all the time you saved not having to think through that simplistically "contrived" problem! Heh.
Anon-y-mous Cow-ard
Thursday, May 20, 2004
CallRecursion(Object)
if Object.HasChilden.WillThrowError then
ShowMessage('Programmer is an idiot ~ WTF is that?')
now exit
elseif Object.HasChildren then
with each Child of Object
CallRecursion(Child)
next
else
CallProcessItem
end
end
ROFLMAO
Thursday, May 20, 2004
Guys,
Thanks for the replies. Yea, I want to avoid the old standard Towers of Hanoi, b/c I don't want to confuse the person. Most people here might have been "natural programmers", but I am just looking for an example for the everyday "idiot", who ,may not be so puzzle inclined. Hence, I want to avoid all the array sort routines also, as they are the natural application of recursion (after fib(), fact(), etc)
Let me consider a binary tree search, or the directory search. I remember examining a "maze" algorithm once, (calculating possible moves or something), and this may be a good example as well.
Bella
Thursday, May 20, 2004
A simple example is just binary search. It avoids the details of a tree structure for the class. Also, binary search can be very effectively demonstrated if you have an old telephone book and you want to search for name. Just keep ripping the book in half and throwing half away.
Stephen Depooter
Friday, May 21, 2004
 Recent Topics
Fog Creek Home
| 
