Recursion in C
Recursion
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 is reached that does not require a self-call.
What is needed for implementing recursion?
-
Decomposition into smaller problems of the same type
-
Recursive calls must diminish problem size
-
Necessity of a base case
-
Base case must be reached
Base Case
An instance of a problem whose solution 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.
Purpose of Base Case
-
Terminating condition:
Without an explicitly defined base case, a recursive function would call indefinitely. -
Building block of solution:
A recursive function determines its solution from the base cases it reaches.
Example
Function Call
Output
Advantages of Recursion
-
Recursive functions make the code look clean and elegant.
-
A complex task can be broken down into simpler sub-problems.
-
Sequence generation is easier with recursion than using nested iteration.
Disadvantages of Recursion
-
Sometimes the logic behind recursion is hard to follow.
-
Recursive calls are expensive (inefficient) as they take up more memory and time.
-
Recursive functions are hard to debug.
Example Programs
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 ( Euclid's Algorithm)
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)
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;
}
Comments
Post a Comment