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?
Bella
http://discuss.fogcreek.com/joelonsoftware/
Edward
LOL!
Philo
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.
John C.
>>What about traversing a filesystem hierarchy
Albert D. Kallal
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
Hmmm....
The One You Loved (TOYL)
+1 for binary trees
Dennis Atkins
I always liked the pocket telescope (i.e., expandable telescope) analogy. The simple visual image helped me understand recursion immediately.
yet another anon
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:
Tayssir John Gabbour
+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.)
Sam Livingston-Gray
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
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.
Julian
I learnt recurssion using the towers of hanoi.
Aussie Chick
"My grandmother, who lived to be 97, explained it this way, 'The way to understand recursion is to understand recursion.'"
offMyMeds
I first grasped recursion when trying to write a flood-fill function for graphics. It looked something like this (pseudo-python syntax):
Chris Tavares
Populate a TreeView control on a form using recursion. That way they can 'see' how it works...
GiorgioG
traversing a labyrinth
Michael Moser
To understand recursion, yo have to understand recursion..
Yablan
Hey offMyMeds,
Martin A. Bøgelund
Actually, my favorite metaphor for introducing recursion is that it's all about being Lazy:
John C.
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
Someone mentioned the knight's tour chessboard problem.
SteveM
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
For a good solid real world problem you can't beat the file system.
Ged Byrne
Just about anything in Haskell.
KayJay
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.
Tim H
All this recursion talked reminds me of a little Internet bubble problem I encountered....
Herr Herr
"To understand recursion, yo have to understand recursion.."
NoName
Just try to visualize a snake eating it's own tail, until it gets nauseous.
int Me() { Me(); }
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...
Matt
fractals
Yo
Recursive routines tend not to run for ever (or rather its a bug if they do) because for practical purposes its a finite universe.
Simon Lucy
This tutor is fun:
Rikard Linde
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:
Christopher Wells
Oh yes, and fractals! good point.
Matt
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?)
Eric Lippert
"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.
Eric Lippert
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
Une Ternal,
Pakter
Eric
as
What about some XML parsing exercise?
MilesArcher
Eric - the problem is contrived, or the solution is?
Philo
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
CallRecursion(Object)
ROFLMAO
Guys,
Bella
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
Fog Creek Home |