Recursion

Thinking Recursively

Step 3: Find solutions to the simplest inputs.
To make sure that the recursion comes to a stop, you must deal with the simplest inputs separately.
Sometimes you get into philosophical questions dealing with degenerate inputs: empty strings, shapes with no area, and so on.
You may want to investigate a slightly larger input that gets reduces to a degenerate input and see what value you should attach to the degenerate input yields the correct answer.
The simplest strings for the palindrome test are:
- strings with two characters
- strings with a single character
- the empty string.
We don't need a special case for strings with two characters - by removing both the first and last characters, it becomes a string of length 0.
A single character string is a palindrome.
An empty string is a palindrome.