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:

a

_{n}= n*a_{n-1}a

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

a

and a

a

and a

a

So like this we can write

a

a

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

a

_{3}= 3*a_{2}and a

_{2}is equal to 2 times a_{1}a

_{2}= 2*a_{1}and a

_{1}is 1a

_{1}= 1*(This is the base case)*So like this we can write

a

_{2}= 2*1a

_{3}= 3*(2*1) = 6And 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

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.

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.

I just started a class in C++.

ReplyDeleteMy girlfriend has a C++ class. Sounds so confusing to me. :x

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

ReplyDeleteFinnaly found a blog that helps me out thanks for making this kinda tuts man :D

ReplyDeleteUseful tutorial! Thanks!

ReplyDeleteGlad 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.

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

ReplyDeleteNice, I needed this

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

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

ReplyDeleteooooo great blog. :D

ReplyDeleteI.....don;t understand

ReplyDeletegnnnnn ;w;

ReplyDeleteReminds me of my days in computer programming. Sweet blog

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

ReplyDelete