Skip to main content

Recursion in C


Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
It is legal for one function to call another, and you have seen several examples of that. It is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

A recursive function is one that calls itself directly or indirectly to solve a smaller version of its task until a final call which does not require a self call.

What is needed for implementing recursion?
Decomposition into smaller problem of same type.
Recursive calls must diminish problem size.
Necessity of base case
Base case must be reached
Base case
An instance of a problem, the solution of which requires no further recursive calls is known as a base case. It is a special case whose solution is known. Every recursive algorithm requires at least one base case in order to be valid. A base case has two purposes
·         It acts as a terminating condition. Without explicitly defined base case, a recursive function would call indefinitely.

·         It is a building block to the complete solution.ie; a recursive function determines its solution from the base cases it reach.

For example, look at the following function:
void countdown(int n)
if  (n == 0)
  printf( "Blastoff!");
else
   printf(“%d”,n);
   countdown(n-1);

A call to this function countdown(5) will print
5
4
3
2
1
Blastoff!
Advantages of recursion
Recursive functions make the code look clean and elegant.
A complex task can be broken down into simpler sub-problems using recursion.
Sequence generation is easier with recursion than using some nested iteration.
Disadvantages of recursion
Sometimes the logic behind recursion is hard to follow through.
Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
Recursive functions are hard to debug.

Try the Examples
1.Reverse a string
void reverse(char *s)
{

if ( *s)
   {
    reverse(s+1);
    printf(“%c”,*s);
}
}
2.Printing backward.Enter characters and "." to stop
void printback()
{
char c;
scanf("%c",&c);
if (c!='.')
  {
    printback();
    printf("%c",c);
  }
}
3.Finding Length of a string
int reclen(char *str)   
{
       if (*str == '\0')
        return 0;
    else
        return 1 + reclen(str + 1);
}
4.Factorial of an integer
long int fact(int n)
{
If(n<0)
   {
   printf(“error –ve argument to factorial\n”);
   exit(1);
   }
else if ( n==0)
           return 1;
        else
           return(n*fact(n-1));

}
5.nth Fibonacci number
int fib(int n)
{
If ( n<=2)
   return 1;
else
 return(fib(n-1)+fib(n-2));
}
6.Gcd of two numbers
int gcd(int a,int b)
{
int r;
r=a%b;
if(r==0)
return b;
else
            return gcd(b,r);
}
7.power x^k using recursion
float power(float x,int k)
{
if (k<0)
            {
            printf(“cannot raise –ve exponent\n”);
            exit(1);
            }
else if(k==0)
            return(1.0);
else
            return(x*power(x,k-1));
}
8.Convert decimal to binary
int convert(int n)
{
if (n!=0)
 {
 printf(“%d”,convert(n/2));
return (n%2);
 }
else
 return 0;
}
9.sum of n elements of an integer array
int sum(int a[],int n)
{
if(n==1)
 return a[0];
else
 return(a[n-1]+sum(a,n-1);
}
10.Sum of n natural numbers
int  sum(int n)
     if (n ==0)
       return 0;
     else
       return n + sum(n-1);
11. Sum of the digits of a number
int  sumd(int n):
     if (n == 0)
        return 0;
     else:       
        return (n%10 + sumd(n/10) );
12.Recursive functions to solve x^n+x^n-1+x^n-2+…..+x^1
long power(long x,int exp)
{
if (exp<=0)
 return 1;
else
 return(x*power(x,- - exp));
}
long sumrec(int n,int x)
{
if(n!=0)
{
 return(power(x,n)+sumrec(--n,x));
}
return 0;
}
13.Recursive binary search( return -1 if key is not present in array a[] or return the position)
void binsearch(int a[],int key,int low,int high)
{
   int mid;
   if(low>high)
    return -1;
   mid=(low+high)/2;
   if(a[mid]==key) return mid;
   else if(key>a[mid]) return(binsearch(a,key,mid+1,high));
   else return(binsearch(a,key,low,mid-1));
}



Comments

Popular posts from this blog

Files in C

A file is a repository of data that is stored in a permanent storage media, mainly in secondary memory. In order to use the files we should learn how to read information from a file and how to write information into a file. A very important concept in C is the stream.The stream is a common logical interface to the various devices( files).A stream is linked to a file while using an open operation. A stream is disassociated from a file while using a close operation. The current location, also referred to as the current position, is the location in a file where the next fie access will occur.There are two types of streams text and binary. The following are some difference between text and binary files ·Text file is human readable because everything is stored in terms of text. In binary file everything is written in terms of 0 and 1, therefore binary file is not human readable. ·A newline(\n) character is converted into the carriage return-linefeed combination before being written to the d…

KTU C programming question paper and evaluation scheme

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY SECOND SEMESTER B.TECH DEGREE EXAMINATION, MAY 2017 CS 100 COMPUTER PROGRAMMING (CS, IT) SCHEME OF EVALUATION
PART A 1 An identifier is a sequence of characters invented by the programmer or to identify or name a specific object. The sequence of characters may be letters, digits, and special character ‘_’known as an underscore Rules: i)Identifiers should start with alphabets. ii)Identifiers are case sensitive iii)A numeric digit should not be the first character iv)Identifier name should not be a keyword v)Identifier may be of any reasonable length 1mark






2mark 2 Associativity defines the direction, left to right or right to left in which operator act upon its operands Unary operators have associativity is from right to left. For examplein the expression &--x, pre decrement works first and then address of operator works Direction + example<

Strings in C

Strings in C Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’. Declaration of strings: Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string. charstr_name[size]; In the above syntax str_name is any name given to the string variable and size is used define the length of the string, i.e the number of characters strings will store. Please keep in mind that there is an extra terminating character which is the Null character (‘\0’) used to indicate termination of string which differs strings from normal character arrays. Initializing a String: A string can be initialized in different ways. We will explain this with the help of an example. Below is an example to declare a string with name as str and initialize it with “cek”. 1. charstr[] = "cek"; 2. charstr[50] = "cek"; 3. charstr[] = {'c','…