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<

Linear and Binary Search in C

Searching is one of the most common problems that arise in computing. Searching is the algorithmic process of finding a particular item in a collection of items. A search typically answers either True or False as to whether the item is present. On occasion it may be modified to return where the item is found. Search operations are usually carried out on a key field. Consider searching for a given value k in an array A of size n. There are 2 basic approaches: sequential search and binary search.
Linear (Sequential) Search When data items are stored in a collection such as a list or array , we say that they have a linear or sequential relationship. Each data item is stored in a position relative to the others. In C array, these relative positions are the index values of the individual items. Since these index values are ordered, it is possible for us to visit them in sequence. This process gives rise to our first searching technique, the sequential search. Starting at the first item in …