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!
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.
I spent an hour or so today playing out with pieces of paper how that could be done. Lots of fun!!