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);

}

}

void printback()

{

char c;

scanf("%c",&c);

if (c!='.')

{

printback();

printf("%c",c);

}

}

int reclen(char *str)

{

if (*str == '\0')

return 0;

else

return 1 + reclen(str + 1);

}

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

^{th}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

## Post a Comment