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.Print natural numbers less than 50. Call this function numPrint(1)

int numPrint(int n)

{

    if(n<=50)

    {

         printf(" %d ",n);

         numPrint(n+1);

    }

}

2.Reverse a string
void reverse(char *s)
{
if ( *s)
{
reverse(s+1);
printf(“%c”,*s);
}
}
3.Printing backward.Enter characters and "." to stop
void printback()
{
char c;
scanf("%c",&c);
if (c!='.')
{
printback();
printf("%c",c);
}
}
4.Finding Length of a string (university question)
int reclen(char *str)
{
if (*str == '\0')
return 0;
else
return 1 + reclen(str + 1);
}
5.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));
}
6.nth Fibonacci number
int fib(int n)
{
If ( n<=2)
return 1;
else
return(fib(n-1)+fib(n-2));
}
7.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);
}
8.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));
}
9.Convert decimal to binary
int convert(int n)
{
if (n!=0)
{
printf(“%d”,convert(n/2));
return (n%2);
}
else
return 0;
}
10.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);
}
11.Sum of n natural numbers
int sum(int n)

{  
if (n ==0)
return 0;
else
return n + sum(n-1);

}  
12. Sum of the digits of a number
int sumd(int n)

{
if (n == 0)
return 0;
else
return (n%10 + sumd(n/10) );

}  

13.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;
}
14.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));
}

15.Fibonacci Series using recursion ( university question) 

#include<stdio.h>
int Fibseries(int n)
{
if ( n == 0 )
return 0;
else if ( n == 1 )
return 1;
else
return ( Fibseries(n-1) + Fibseries(n-2) );
}
int main()
{
int n, i = 0, c;
printf("Enter n...number of terms in the series..\n);
scanf("%d",&n);
printf("Fibonacci series\n");
for ( c = 1 ; c <= n ; c++ )
{
printf("%d\n", Fibseries(i));
i++;
}
return 0;
}

16.Counting number of digits( Note that this function uses a static variable)

#include <stdio.h>

int noofdigits(int n)

{

    static int count=0;

     if(n!=0)

     {

          count++;

         noofdigits(n/10);

    }

    return count;

}

int main()

{ int n;

printf("Enter a number \n");

scanf("%d",&n);

printf("No of digits=%d",noofdigits(n));

}

17.Largest array element

#include <stdio.h>

int lararryelmnt(int arr[],int n)

{

    static int i=0,large=0;

    if(i < n)

    {

         if(arr[i]>large)

           large=arr[i];

      i++;

      lararryelmnt(arr,n);

    }

    return large;

}

int main()

{ int n,i,arr[100];

printf("Enter n \n");

scanf("%d",&n);

printf("Enter array elements\n");

for(i=0;i<n;i++) scanf("%d",&arr[i]);

printf("Largest array element is=%d",lararryelmnt(arr,n));

}

18.Prime or not using recursion ( Note that this program uses a global variable i)

#include <stdio.h>

int Prime(int);

int i;

int main()

{

    int n,flag;

printf("\n\n Recursion : Check a number is prime number or not :\n");

printf("--------------------------------------------------------\n");

    printf(" Input any positive number : ");

    scanf("%d",&n);

    i = n/2;

    flag = Prime(n);//call the function  Prime

   if(flag==1)

        printf(" The number %d is a prime number. \n\n",n);

   else

      printf(" The number %d is not a prime number. \n\n",n);

   return 0;

}

int Prime(int n)

{

    if(i==1)

    {

        return 1;

    }

    else if(n %i==0)

    {

         return 0;

    }     

    else

       {

         i = i -1; 

         Prime(n);//calling the function Prime itself recursively

      }

}

19.Even and odd numbers up to n

void EvenAndOdd(int stVal, int n)

{

    if(stVal > n)

        return;

    printf("%d  ", stVal);

    EvenAndOdd(stVal+2, n);//calling the function EvenAndOdd itself recursively

}

int main()

{

    EvenAndOdd(1,50);

    EvenAndOdd(2,50);

}

20.copy one string to another

#include <stdio.h>

void copyString(char stng2[], char stng1[], int i)

{

    stng2[i] = stng1[i];

    if (stng1[i] == '\0')

        return;

    copyString(stng2, stng1, i + 1);

}

int main()

{

    char stng1[120], stng2[120];

    printf("\n\n Recursion : Copy One string to another :\n");

printf("---------------------------------------------\n");

     printf(" Input the  string to copy : ");

    gets(stng1);

    copyString(stng2, stng1, 0);

    printf("\n The string successfully copied.\n\n");

    printf(" The first string is : %s\n", stng1);

    printf(" The copied string is : %s\n\n", stng2);

    return 0;

}

Programs to try

1.Write a recursive factorial function. Use this to find  nPr and nCr

2.Write a recursive function to find the n'th Fibonacci number.Use this function to generate Fibonacci series.

3.Write a recursive function to find gcd of two numbers.

4.Reverse a number using a recursive function.

5.Use a recursive function to find the sum of the digits of a number.

6.Find the sum of first n natural numbers using a recursive function.

7.Find sum of n elements in an integer array using recursion.

8.Convert a decimal number to binary using a recursive function.

9.Write a recursive function to find x^k ( power(x,k)).

10.Use the above function to covert binary number into decimal.

11.Implement binary search using a recursive function.