Recursion In Programming


Recursion and recursive functions are a great concept in programming languages. For a beginner it can turn into one of the worst nightmares but once you get into the spirit of programming then writing recursive programs will be a bliss. Recently some of my friends found it difficult to write a recursive program to print the Fibonacci series upto a limit. This is what inspired me to write a small post on recursive functions. My post will be based on C programming. I am not an expert to write a large post on recursive functions but I would like to share with you some interesting things I know on recursion.

Recursion is nothing but the breaking up of a large problem into smaller problems. It is a divide and conquer policy. Here the smaller programs are defined in terms of the larger program, or we can say that a single function calls itself till a base condition is reached.

A recursion

A recursion

This picture should serve as an example as to what recursion is (How to make such a picture I will explain in some other post)

All recursive functions consist of two parts

  • A base case
  • A recursive step

It is the recursive step that is defined in terms of itself and it must move closer to the base case. If there is no base case or the recursive step does not reach the base case the program may run infinitely or till it runs out of memory. Almost all iterative programs can be done as a recursive program. Another classical example of solving a problem with recursion is the tower of Hanoi. Read more about it here http://familycoding.com/2012/04/12/tower-of-hanoi/

Recursive functions can make your program look more shorter and neater. But debugging and understanding a recursive program can be a difficult task. But the trick is to identify the base case and the recursive steps.

Here I will demonstrate the Fibonacci series example with and without recursion. Before you look into the program I suggest reading http://braintenance.blogspot.in/2011/08/fibonacci-numbers-math-meets-mysticism.html to really understand the fun in Fibonacci series.

The Code below shows Fibonacci series Without recursion

#include<stdio.h>
int main()
{
  int a=0,b=1,c,i,n;
  printf("Enter the number of elelments of fibonacci series needed\n");
  scanf("%d",&n);
  printf("\n %d  ",b);// to display the initial 1 of series
  for(i=0;i<n-1;i++)
    {
      c=a+b;
      printf("\n %d  ",c);
      a=b;
      b=c;
    }
  printf("\n\n");
  return 0;
}

The Code below shows Fibonacci series with recursion

#include<stdio.h>
int main()
{
  int n,a=0,b=1;
  printf("\n Enter the number of elements of Fibonacci series to be displayed = ");
  scanf("%d",&n);
  printf("\n %d  ",b);// to display the initial 1 of series
  fib(a,b,n-1);
  printf("\n********************************************\n");
  return 0;
}
int fib(int a,int b,int n)
{
  if(n!=0)
    {
      printf("%d  ",(a+b));
      n--;
      fib(b,a+b,n);
    }
  else
    {
      return 0;
    }
}

So much has been said about Recursive functions but any post on recursion would be misleading if I leave out the following points.

  • Recursive programs are less efficient as more memory space is used each time a function is called.
  • Iterative programs are less time-consuming and easier to write.

Despite that recursion can be fun and can really turn you on if you are a coding maniac.


Advertisements

About vineethkartha

Hi, I am Vineeth Kartha, I hold a Masters degree in Embedded Systems from BITS Pilani, Goa Campus. I currently work as a Software Developer. I am A free software promoter and electronics hobbyist. In my free time I do a little bit of birding and Wildlife photography. I love travelling, reading and blogging.

Posted on May 19, 2012, in Technical and tagged , , , , . Bookmark the permalink. 4 Comments.

  1. Undeniably consider that which you said. Your favourite reason appeared to be at the internet the simplest factor to take note of. I say to you, I definitely get irked whilst folks think about worries that they plainly do not realize about. You controlled to hit the nail upon the top and also outlined out the entire thing without having side-effects , other folks could take a signal. Will probably be back to get more. Thanks

  2. Great Stuff, do you have a facebook profile?

  3. The information in this article is one-of-a-kind. You have far surpassed all the other writers with your knowledge of this subject. I share your unique views. Thank you for taking time to get this right. http://www.samsung1080phdtv.net/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: