What is Recursion? How to Write a Recursive Function? Part 2
Airfare Daily Deals eCigarettes Eyeglasses Hotels Jewelry Online Backup Online Dating Online Printing Online Tickets Skin Care Textbook Rentals Vitamins Web Hosting Weddings
Find thousands of shopping-related forums
SEARCH

What is Recursion? How to Write a Recursive Function? Part 2

This two part article series explains the concepts of recursion and also illustrates how to write a recursive function with an example.

(contd. from part 1)

However, there are a few things which need to be taken care of while writing recursive function. The recursive call statement - the one which calls the function itself, should be conditional. Or else, when the function would be called, it will keep on calling itself again and again - causing an Infinite recursion - creating new contexts each time. This would ultimately eat up all the memory available and you will get a Stack Overflow error.

The condition itself should be converging, i.e. each call should bring you closer to finish off the recursive calls. If the call diverges, than even after having a conditional recursive call, you would have infinite recursion.

Let's write a recursive function for displaying the first n natural numbers. The first time the function is called, you would send it an argument 'n' - the number of natural numbers to be displayed. Now, the function should display one natural number and then pass on the task recursively to second function call - but there should be a condition - which should converge - each time a number is displayed, the original 'n' should be decremented. (Try writing this conditional statement yourself before you read on)

Generally, we would need a counter, to keep record of the numbers already displayed, numbers remaining to be displayed - so that once all the numbers are displayed, we can finally stop the recursion and return to the calling function. But in this case, n can act the counter too. We'll simply display n and call the function again with n-1.

Our condition would be,

if (n>0) {

   printf("%d", n)

   display_n(n-1);

}

Here, display_n is the recursive function. So the entire function would be:

void display_n(int n){

if (n>0) {

printf("%d", n);

display_n(n-1);

}

}

Say you want to call the function from another function, the function call would be,

display_n(5);

to display the first 5 natural numbers - 5 4 3 2 1

This function would display the natural numbers in reverse order. In order to display them from 1 to n, you'll have to use a counter. Try writing that program as an exercise.

While this code would work, it's in not a very effective example to illustrate the power of recursion. You could have written a simple loop for the same task, which would do the job in one function call. In fact the above code would essentially require n function calls to display n numbers! Not very optimized. But this was just for concept illustration.

An example where Recursive calls are very useful and powerful is tree traversal - recursion is in fact a natural way of traversing a tree and a natural way of implementing a lot of other algorithms. Start on your way with simple programs like factorial, fibo nacci, and then you'll be prepared to traverse a tree recursively.

Need an answer?
Get insightful answers from community-recommended
experts
in Computer Programming & Languages on Knoji.
Would you recommend this author as an expert in Computer Programming & Languages?
You have 0 recommendations remaining to grant today.
Comments (0)
ARTICLE DETAILS
RELATED ARTICLES
ARTICLE KEYWORDS