Help me design a class project!

Hey guys, I have to design a difficult, two-week project on recursion for the first semester programming class I'm teaching. But I'm having a hard time finding something that's difficult yet doesn't require any data structures except for linked lists (which is all they would have learned at this point).

For an example, last semester they had to decrypt a message, where the encrypted message was made by substituting letters, e.g. substituting every "a" for a "c". They were given an encrypted message and a dictionary of words that could appear in the solution. They had to take one encrypted word and figure out a substitution that would yield a valid word. Using that substitution (e.g. maybe they decided that all a's were substituted with c's) they had to solve the rest of the message. If they reached a point where they had a word that was not in the dictionary, then they must have made an invalid substitution and had to back out of the recursion and try again. (Maybe the c's in the encrypted message were actually e's, not a's.) We gave them no skeleton code for this project; they had to do it all themselves. But I can give them some skeleton code for this project if necessary.

If you have an idea, please do not post a solution in case a student stumbles upon this site. Just state the problem as if you were assigning it to your students and I'll figure out the solution. ;) It just has to be something a lot more complicated than the standard write a recursive function to calculate n! -- it needs to take them a full 2 weeks.

Thank you!

>something that's difficult yet doesn't require any data structures except for linked lists
Implement a linked list library with recursive internals. :D To make it more difficult, require them to maintain a free store of nodes (usually implemented as linked list) as an optimization for memory management.

2 weeks for recursion? eesh... my programming class gave us a day, at most, to learn it. of course, its not a semester long class either :-\

i dont know if this is a 2-week worthy assignment, but how about implimenting quicksort? i wrote a quicksort algorithm that would sort a linked list where the next pointers get rearranged to order the list in the way specified by the user (by passing in a compare function). maybe have this as part of the link list library mentioned by prelude...

Difficult and with linked lists... maybe their own version of a string class with simple operators etc?

Although there might not be much recursion in that... hm.... what about the towers of Hanoi :) I spent an hour or so today playing out with pieces of paper how that could be done. Lots of fun!!:D:D

Thanks for the suggestions!

Prelude, may I ask what recursive internals are? I don't think I've heard that term before.

quicksort would definitely be too easy for a project, that would be something they might whip up in lab. I wish they knew trees or something so I could think of something really nasty!

Towers of Hanoi is a possibility, but I would be worried that they might find the algorithm or even some code online for such a well-known problem.... sigh ... this may be a harder project to design than I thought!

Any other suggestions? Thanks!

What about the 8-queens problem? Or if you want to mix it up, the knight's tour. Those are pretty good.

Edit: You can easily extend it to an n-queens problem.

>Prelude, may I ask what recursive internals are? I don't think I've heard that term before.
Instead of using loops to implement operations like insertion and deletion, use recursion.