HowToProgramC : Lesson 13


Back Home Next



Recursive Function:

This is the special type of function which can call itself. What kind of function it would be? There are many problems and specific areas where you can see the repetitive behavior (pattern) or you can find a thing, which can be modeled in such a way that it repeats itself.

Let us take a simple example of x10, how will we calculate it? There are many ways of doing it. But from a simple perspective, we can say that by definition:

x10= x * x9

So what is x9? It is x9 = x * x8 and so on.
We can see the pattern in it:

xn = x * xn-1

To compute it, we can always write a program to take the power of some number. How to do it? The power function itself is making recursive call to itself. As a recursive function writer, you should know where to stop the recursive call (base case). Like in this case, you can stop when the power of x i.e. n is 1 or 0.

Similarly, you can see lot of similar problems like Factorials. A factorial of a positive integer ‘n’ is defined as:

n! = (n) * (n-1) * (n-2) * ….. * 2 * 1

Note that

n! = (n) * (n-1)! and

(n-1)! = (n-1) * (n-2)!

This is clearly a recursive behavior. While writing a factorial function, we can stop recursive calling when n is 2 or 1.

long fact(long n)
{
if (n <= 1)
return 1;
else
return n * fact(n-1);
}

Note that there are two parts (branches) of the function: one is the base case ( which indicates when the function will terminate) and other is recursively calling part.

All the problems can be solved using the iterative functions and constructs we have studied until now. So the question is:

Do we need to use recursive functions?

Yes, it adds little elegance to the code of the function but there is a huge price to pay for this. Its use may lead to the problems of having memory overhead. There may also be stacking overhead as lots of function calls are made. A lot of functions can be written without recursion (iteratively) and more efficiently.

So as a programmer, you have an option to go for elegant code or efficient code, sometimes there is a trade-off. As a general rule, when you have to make a choice out of elegance and efficiency, where the price or resources is not an issue, go for elegance but if the price is high enough then go for efficiency.

‘C’ language facilitates us for recursive functions like lot of other languages but not all computer languages support recursive functions. Also, all the problems can not be solved by recursion but only those, which can be separated out for base case, not iterative ones.



Back Home Next


Google




learntoknow@yahoo.com
© All rights Reserved.