What is recursion, and can I see an example?

OK, you have to think about like this:

let's think about n factorial, or n!:

1. Define a base case, or for our example:

if n = 0, n! = 1;

2. Define a recursive case:
if n > 0, n! = n * (n - 1)!
or, n factorial equals n times n-1 factorial

Think about this, we'll do an example:

take 4, 4!, using our recursive steps, is:
4! = 4 * 3!
4 * 3! = 4 * 3 * 2!
4 * 3 * 2! = 4 * 3 * 2 * 1!
4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 * 0!
and, since 0! = 1, we have
4 * 3 * 2 * 1 * 1, or 4 * 3 * 2 * 1, which is the definition of factorial. In c, you would write this as:

int factorial (int n){
if (n == 0)
return 1;
else
return (n * factorial(n-1));
}

This will use the stack, and call itself until we reach the base case. The base case is very important, you must ensure that you will reach the base case. In the previous example, I know we won't be stuck in an infinite loop because each time we call the function we are decrementing n.