So, let’s test some values to see if this is true. First, we know that factorial(0) (from here on abbreviated as fact(n)) equals 1, by the base case given in the definition.

     We can see that this recursive definition is giving the correct answer. Or at least it gave the correct answer for the cases we checked. You can never know if the definition you’ve found is valid for all n unless you prove it, preferably with mathematical induction. But that's beyond the scope of this tutorial.

     So, now that we’re convinced that this truly is the recursive definition of factorial, we must ask: "how did someone figure that out?" One explanation is divine/extraterrestrial intervention (depending on your particular cosmology). However, if you put divine intervention down as a proof on a test, the teacher is more likely to count it wrong than to debate philosophy with you. We’ll need some more solid ground than that to stand on.

     Well, as stated in the description of a recursive definition, a base case and inductive rule were needed. In this case, fact(0)=1 is the base case. This is a logical place to start, seeing as how the n in fact(n) must be larger than or equal to 1 (only positive integers). The other half is the inductive rule of the problem, which in this case is represented by “fact(n)=fact(n-1)*n”. We can see the logic in this, as the factorial of any number, is simply the factorial of the number one smaller than it, times the number you’re finding the factorial of. For example:

10! = 10*9*8*...*2*1 = 10*(9*8*7*...*2*1) = 10*9!

To help you better understand factorials, experiment with the applet below.

     Some examples of palindromes are "abba", "radar", and "mom". Also important for the definition of a palindrome, we must see that the empty string and a single letter are also palindromes. Now we must set at the task of figuring out how to write a general, all-encompassing set of rules that can define all palindromes that can be formed using the English alphabet.

     So first, we obviously need a base case. Since we defined the smallest palindrome as the empty string, by the examples we’ve seen so far, we should define the basic palindrome as the empty string. This is actually incorrect, but we’ll come back to why after we explore a little bit more. Now that we have a base case, what will we use for an inductive rule for palindromes? I’ll give you a hint, the answer is not yellow or threeve. Ok, ok, I’ll give a real hint: we said that the recursive/inductive rule defines an object in terms of an object of identical configuration but smaller size.

     In order to see the answer, we have to make the observation that a palindrome of length L is simply a palindrome of length (L-2) with an identical character at the beginning and end of the string. In other words, our definition would give the following:

     The string "abba" is the string "bb" with an ‘a’ at the beginning and end of the string. And the string "bb" is the empty string with a ‘b’ at the beginning and end. Since the empty string is a palindrome, "bb" is a palindrome, and therefore "abba" is a palindrome.

     But what about "zxyxz"? This is obviously a palindrome, but we won’t end up with an empty string, we’ll end up with the string "y" with an ‘x’ on either side. We cannot subtract two characters from the string again, without getting a string of negative length (just plain silly). Therefore, we must need to change our base case. The current base definition of a palindrome works for strings of even length, but what about odd length palindromes? Just as in mathematical induction (to which recursive definitions have many parallels), one must cover all the necessary base cases. We simply need to say that the basic palindrome is the empty string or string of length 1. Now, since "y" is a palindrome, "xyx" is a palindrome, and "zxyxz" is a palindrome.