Recursion problems

[elee...@gmail.com]

1. Poking around on the interwebs for some recursion problems, and I
found a few questions at this website:

http://faculty.washington.edu/wconlen/tcss143/Labs/RecursionProblemsLab.html

I was wondering if the recursion portion of the exam is like those
problems or more like "find a way to count the size of a blob" (more
real-world-esque?). or like this problem:

Problem 1.6: A palindrome is a sequence of characters or numbers that
looks the same forwards and backwards. For example, "Madam, I'm Adam"
is a palindrome because it is spelled the same reading it from front
to back as from back to front. The number 12321 is a numerical
palindrome. Write a function that takes a string and its length as
arguments and recursively determines whether the string is a
palindrome: int ispalindrome(char *s, int len);

(from http://www.sparknotes.com/cs/recursion/examples/problems1.html)

2. Would we need to write a recursion method or just describe how to
do something recursively, or both?

[Greg]

> I was wondering if the recursion portion of the exam is like those
> problems or more like "find a way to count the size of a blob" (more
> real-world-esque?). or like this problem:

Strategies such as flood-fill (the blob problem) and backtracking are
certainly very important. You should know how they work, why they
work, and when they are good solutions and why. You should be able to
apply them as appropriate to real problems. But, because of time
constraints, we aren't likely to ask you to code an entire solution to
one of these problems. And, even coding part of a solution in an
existing framework probably requires more reading than it is worth.

If we ask you to code within a framework, it is likely to be something
of eduring value, such as one of the important, canonical data
structures.

> Problem 1.6: A palindrome is a sequence of characters or numbers that
> looks the same forwards and backwards. For example, "Madam, I'm Adam"
> is a palindrome because it is spelled the same reading it from front
> to back as from back to front. The number 12321 is a numerical
> palindrome. Write a function that takes a string and its length as
> arguments and recursively determines whether the string is a
> palindrome: int ispalindrome(char *s, int len);

This is a nice problem, but is a very well known classic. So, we
wouldn't use it. But, some elements of it are very interesting. For
example, it is a short, easily managable recursive problem. And, it
makes use of the stack property in an interesting way.

> 2. Would we need to write a recursion method or just describe how to
> do something recursively, or both?

Both are definitely fair game.