Sunday 13 March 2011

Recursion

Probably one of the more controversial topics in terms of usefulness. Today, I'll show you how to write some simple recursive functions and in an upcoming post, I'll show you guys how it can be useful outside of mathematical applications.
So first off, what exactly is a recursive function. A recursive function is a function that keeps calling itself, until it reaches a base case. Once the base case is reached, then the function calls will return all the values to the previous function calls until the original call to the function returns its value.
This sounds like a lot, but I'll explain it using examples. First, let's look at the factorial function.
For example, we know that:

4! = 4*3*2*1 = 24
5! = 5*4*3*2*1 = 120
etc.

Written as a recurrence relation, the factorial function looks like:

an = n*an-1
a1 = 1

So let's say we wanted to find the 3rd element in this relation, a3. It will be equal to 3 times a2

a3 = 3*a2

and a2 is equal to 2 times a1

a2 = 2*a1

and a1 is 1

a1 = 1    (This is the base case)

So like this we can write

a2 = 2*1
a3 = 3*(2*1) = 6

And we have our answer!
This is how a recursive function works. See how the function would keep "calling" itself until it reached a base case that was not a recursive call?
Now let's see how we can apply this as a function in C.

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

Notice how each time a recursive call is made, we first check to see if n is our base case, and if not, we do recursive calls. Of course, this code is buggy in that if we passed a negative number into the function, it would loop forever, but simple modifications can fix that.
So now that you've seen how it's done, you may be wondering how it works.
Every time a recursive call is made, the scope of the previous call is held in memory and "awaits" an answer from the call that it made. With the example earlier where we calculated 3!, the first call, makes a another call which then makes another call. The 3rd call will return the base case which then gets multiplied by 2 and returned to the first call. The original call then multiplies 2 by 3 and then returns the value to wherever the original call was made.

Later, I'll show you how to apply recursive functions to practical situations where math is not directly involved.

15 comments:

  1. I just started a class in C++.

    ReplyDelete
  2. My girlfriend has a C++ class. Sounds so confusing to me. :x

    ReplyDelete
  3. I've been trying to learn C++ for some time now. These tutorials are helpful, keep'em coming

    ReplyDelete
  4. Finnaly found a blog that helps me out thanks for making this kinda tuts man :D

    ReplyDelete
  5. Glad i know how to do this. For those who do not though this is a great post and example to help them learn. Looking forward to more applications shown.

    ReplyDelete
  6. time to start with C++ :) seems like I found great place where I can finally learn awesome blog +followed

    ReplyDelete
  7. I've had so many arguments about recursion over the years, thanks for giving me the hard facts needed to win them.

    ReplyDelete
  8. I study computer science and I don't see how there could be any controversy over the usefulness of recursion.

    ReplyDelete
  9. Reminds me of my days in computer programming. Sweet blog

    ReplyDelete
  10. Did I mention I love you? I'm having some trouble with my Devry course..maybe I can get tutor?

    ReplyDelete