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.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.

Comments

Popular posts from this blog

KTU Mandatory C programs for Laboratory and Solutions

LIST OF LAB EXPERIMENTS 1. Familiarization of Hardware Components of a Computer 2. Familiarization of Linux environment – Programming in C with Linux 3. Familiarization of console I/O and operators in C     i) Display “Hello World”     ii) Read two numbers, add them and display their sum     iii) Read the radius of a circle, calculate its area and display it 4. Evaluate the arithmetic expression ((a -b / c * d + e) * (f +g))   and display its solution. Read the values of the variables from the user through console 5. Read 3 integer values, find the largest among them. 6. Read a Natural Number and check whether the number is prime or not 7. Read a Natural Number and check whether the number is Armstrong or not 8. Read n integers, store them in an array and find their sum and average 9. Read n integers, store them in an array and search for an element in the    array using an algorithm for Linear Search 10.Read n integers, store them in an array and sort the elements in t

PROGRAMMING IN C KTU EST 102 THEORY AND LAB NOTES

PROGRAMMING IN C  KTU  EST 102  THEORY AND LAB   COMMON FOR ALL BRANCHES About Me Syllabus Theory Syllabus Lab Model Question Paper University Question Papers and evaluation scheme Introduction( Lab) Introduction to C programming Linux History and GNU How to create a bootable ubuntu USB stick Installing  Linux Install Linux within  Windows Virtual Box and WSL Linux Basic Features and Architecture Basic Linux Commands Beginning C Programming Compiling C programs using gcc in Linux Debugging C program using gdb Module 1: Basics of computer hardware and software          Module-1 Reading Material Basics of Computer Architecture Hardware and Software System Software and Application Software  Programming Languages ( High level, Low level and Machine Language) and Translators ( Compiler, Interpreter, Assembler) Algorithm, Flowcharts and Pseudo code Program Development Structured Programming Basics of hardware ( video) Know about Motherboard(video) Know Universal Serial Bus ( USB) - video Lea

Input Output-printf() and scanf()

printf() and scanf() function in C   printf() and scanf() functions are inbuilt library functions in C programming language which are available in C library by default.These functions are declared and related macros are defined in “stdio.h” which is a header file in C language. We have to include “ stdio.h ” file as shown in below to make use of these printf() and scanf() library functions in C program. #include <stdio.h>   printf() function in C   In C programming language, printf() function is used to print the “character, string, float, integer, octal and hexadecimal values” onto the output screen. Here’s a quick summary of the available printf format specifiers:   %c           character %d           decimal (integer) number (base 10) %ld         Long integer %e           exponential floating-point number %f           floating-point number %lf          double number %i            integer (base 10) %o         octal number (base 8) %s         a string of characters %u