|Lessons||Lesson 13: Recursive Functions|
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
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
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)
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