Writing Recursive Functions

Recursive functions are sometimes hard to write because we are not used to thinking about problems recursively. However, if we try to keep the following in mind, it will make writing recursive functions a lot simpler. There are two things you should do:

1. state the base case (aka easy case). what argument values will lead to a solution so simple that you can simply return that value (or do a very simple calculation and return that value?
2. state the recursive case. if you are given something other than the base case how can you use the function itself to get to the base case
3. Recursion is about stating a problem in terms of itself. The solution to the current problem consists of taking a small step and restating the problem.

Example: The factorial function.

Write a function that is given a single argument n and returns n!. n! = n*(n-1)*(n-2) ...2* 1. For example 4! = 4 * 3 * 2 * 1 , by definition, 0! is 1

How would you do it recursively?

Lets start with base case. What value of n is it easy to come up with the result of n!?

0 is easy.. by definition 0! is 1. 1 is also easy because 1! = 1

Thus, we can establish that any value 1 or less is a base case with result of 1.

Now, the recursive case... how can we state factorial in terms of itself?

Let's consider this example: $\begin{aligned} 5! &= (5)(4)(3)(2)(1)\\ 4! &= (4)(3)(2)(1)\\ \end{aligned}$

but consider another way to look at $5!$

$5! = (5)\underbrace{(4)(3)(2)(1)}_{4!}$

Thus, we can express above as:

$5! = (5)(4!)$

And in gneral:

$n! = n(n-1)!$

unsigned int factorial(unsigned int n) {
    unsigned int rc = 1 ;           //base case result
    if(n > 1) {                     //if n > 1 we  have the recursive case
        rc = n * factorial(n - 1);  //rc is n * (n - 1)!
    }
    return rc;
}

tip

Recursion works by magic... ok it really doesn't but it might be easier to think of it that way. Essentially what recursion does is it starts with the idea that you already have a working function. (ie factorial already works). The base case actually ensures it does work at least for some values of n. The recursive case is simply using a working function to solve the problem. Don't think about it too much and it will be a lot easier to code.