www.pickatutorial.com Computer Tutorials
Top eBooks: C/C++ | C# | Android | Mathematics | Database | Cloud | Graphics | Networking | Oracle | Hardware | AI
Top Tutorials: C/C++ | C#.NET | PHP MySQL | Java | Java Script | jQuery | HTML | xHTML | HTML5 | VB Script| CSS
Lessons Lesson 13: Recursive Functions Bookmark and Share
Lesson 1
Lesson 2
Lesson 3
Lesson 4
Lesson 5
Lesson 6
Lesson 7
Lesson 8
Lesson 9
Lesson 10
Lesson 11
Lesson 12
Lesson 13
Lesson 14
Lesson 15
Lesson 16
Lesson 17
Lesson 18
Lesson 19
Lesson 20
Lesson 21
Lesson 22
Lesson 23
Lesson 24
Lesson 25
Lesson 26
Lesson 27
Lesson 28
Lesson 29
Lesson 30
Lesson 31
Lesson 32
Lesson 33
Lesson 34
Lesson 35
Lesson 36
Lesson 37
Lesson 38
Lesson 39
Lesson 40
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;
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.

NEXT>>>>>Lesson 14. Arrays

Home - Advertise - Contact - Disclaimer - About Us
© Since 2006 pickatutorial.com -- All Rights Reserved.