Skip to content

Recall Recursion…Feel Its Magic

September 27, 2012

Probably for the first time I am taking a risk of publishing a post on a topic without having much information about it. Probably the people who know more about this can help me in this matter and that’s the reason why I have published this post. (As I have said that I know a very little in this matter I will keep using the word “probably” throughout this post as often as required). It has been a quite some time now that I am getting many thoughts, infact many controversial thoughts from many people about this. Just a couple of days back in one of my M.Sc presentations I was asked by one of my teachers that whether it is possible to implement each and every problem in a recursive way or not. I answered, “Yes”. Then he asked me whether it is possible to write a program that adds two integers recursively. He added,” Is it possible either to write a string recursively into a file that has been given as input by the user”?
I did not face such questions before, neither thought over them. So it was very obvious that I did not have answers to his questions then and there. But after thinking for a while when I was on the way back to my home I felt that I can write the first of the couple of programs. I was right. And as soon as the first one was written it was just a matter of time for the second one to be written as well.
Here is the first one of them:


/*Program to add 2 numbers using recursion*/
#include<stdio.h>
int Sum(int,int);
int main(void)
{
  int a,b;
  printf("\nEnter 2 numbers : ");
  scanf("%d%d",&a,&b);
  printf("\n%d+%d=%d",a,b,Sum(a,b));
  return 0;
}
int Sum(int a,int b)
{
  if(a==0)
   return b;
  if(b==0)
   return a;
  if(a!=0)
   return a+Sum(0,b);
  if(b!=0)
   return b+Sum(a,0);
}

And here’s the second:


/*Program to write a line into a file recursively*/
#include<stdio.h>
void write_to_file(char[],FILE*);
int main(void)
{
  char str[50];
  int i;
  FILE *fp;
  printf("\nEnter a line : ");
  gets(str);
  fp=fopen("f1.xns","w");
  if(!fp)
  {
   printf("\nError in opening file...");
   return 1;
  }
  write_to_file(str,fp);
  fclose(fp);
  printf("\nProgram terminated successfully...");
  return 0;
}
void write_to_file(char s[],FILE *fp)
{
  static int i=-1;
  if(s[++i]=='\0')
   return;
  else
  {
   fprintf(fp,"%c",s[i]);
   write_to_file(s,fp);
  }
}

Since the problems are not themselves recursive in nature a novice may find it a little difficult to write the code as unlike Fibonacci numbers and factorial the initial conditions and the exact recurrence relation is not quite visible. But after putting a bit more thought over it one should be able to find his way through as I have. And for doing so one should think that what could be the sub-operations of the problem doesn’t matter how elementary the problem is. Just like as I have done for the above problem. If you have to write a line to a file, first think about writing a character of the line to the file, and when it is done do the same thing for the next character using the same logic. And isn’t it recursion? It really is!
Even for the problem of adding two numbers, it can be observed that their sum is the other number if one of the numbers is a zero. And if this is your boundary condition then you simply have to call the function by its own with one of the arguments set to zero. Just like you can think 10+20 as 10+ Sum (0, 20). And I am sure those of you who have just heard about this problem for the first time, and at your first impression were wondering about is it either possible or not to write such programs; now must be saying,”Oh!! How easy was that”! And that’s the magic of recursion, every time you see a recursive code and you get the feeling that you should have found the answer yourself. Not even me the exception.
Yes, I agree that there is no need of recursion really since we are trying to implement an elementary operation in terms of the same elementary operation. It is quite obvious that if the + operator is available then why to do all such things instead of simply writing (a + b)? Again we are using that same operator while doing a+ Sum(0,b). Similarly we could have written the whole string by a single fprintf() instead of printing characters using the same fprintf() function. And that’s “probably” the reason why we don’t even bother to think about recursion in order to implement such problems. But isn’t it possible to implement them recursively? It is indeed possible, and not only that but also in a typical recursive fashion having well defined boundary conditions instead of an enforcement recursive calls. Now to all of you my question is just the negation of what I was asked: “Is there any such problem that is impossible to implement recursively”? I will wait for your answers.

Advertisements

From → Academics

5 Comments
  1. arindam permalink

    hmm really useful post……nicely explained…….

  2. Lets shorten your recursive Sum function a bit.

    int Sum(int a,int b)
    {
        if(a)  return a+Sum(0,b);
        else return b;
    }
    

    If you want to call a function from the function itself for atleast one time(to make it recursive), even if it is not needed very much, you can do something like this:

    void forcefully_recursive( int param1, int param2,......., int paramn, int param_force)
    {
           if ( param_force == 0 ) return ;  // just to return without doing anything, in case of recursive call
    
           /* 
                 actual work of the function here
           */
           forcefully_recursive( param1, param2,.....paramn, 0);  // make a recursion just for fun : )
    
    }
    
    • Edit @Barsan Das’s comment and wrap the code with the sourcecode shortcode to make it easier to read.

    • Thanks Barshan Das for your suggestion on Sum() function. No problems with the issue of forcible recursion. It is ever possible. But I was trying to show that for every problem there might be a recursive version of implementation with well defined initial conditions. Forcible recursion doesn’t impose the well defined initial conditions.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: