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.

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.