What is Recursion? How to Write a Recursive Function? Part 2
Browse articles:
Auto Beauty Business Culture Dieting DIY Events Fashion Finance Food Freelancing Gardening Health Hobbies Home Internet Jobs Law Local Media Men's Health Mobile Nutrition Parenting Pets Pregnancy Products Psychology Real Estate Relationships Science Seniors Sports Technology Travel Wellness Women's Health
Browse companies:
Automotive Crafts, Hobbies & Gifts Department Stores Electronics & Wearables Fashion Food & Drink Health & Beauty Home & Garden Online Services & Software Sports & Outdoors Subscription Boxes Toys, Kids & Baby Travel & Events

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
RELATED CATEGORIES
ARTICLE KEYWORDS
RECENT SEARCHES ON KNOJI SHOPPING