Recursion

Recursion

• When a function called, in turn, calls a different function, a linking process occurs. Recursion is a specific case of this process, where a function is referred to as itself.
• Recursive functions can be used effectively to resolve problems where the solution is expressed in terms of sequential application of the same solution to subsets of the problem.

main()
{
printf(“This is an example of recursion.\n”);
main();
}

Output:

This is an example of recursion.
This is an example of recursion.
This is an example of recursion.
‘’
‘’
‘’

This is an example of recursion. The execution ends abruptly, otherwise, the execution will go on indefinitely.

Example:Factorial program

 Factorial using recursion:

#include<stdio.h>
main()
{
int num,factorial;
printf("enter number:");
scanf("%d",&num);
factorial=fact(num);
printf("fact of %d is %d",num,factorial);
}
int fact(int n)
{
int factorial;
if(n==1)
 return 1;
else
 factorial=fact(n-1)*n;
return factorial;
}

Output:

Factorial using non-recursion:

#include<stdio.h>
main()
{
int num;
printf("enter number:");
scanf("%d",&num);
printf("fact of %d is:%d",num,factorial(num));
}
int factorial(int n)
{
int i=0,fact=1;
while(i<n)
{
i++;
fact=fact*i;
}
return fact;
}

Output:

Example: GCD program

GCD using recursion:

# include<stdio.h>
# include<conio.h>
main()
{
int m,n,gcd;
printf("enter m and n values:");
scanf("%d%d",&m,&n);
gcd=recgcd(m,n);
printf("gcd (%d , %d) is: %d",m,n,gcd);
}
recgcd(int m,int n) /* Recursive Function */
{
if(n==0)
 return m;
else
 return recgcd(n,m%n);
}

Output:

GCD using non-recursion:

# include<stdio.h>
# include<conio.h>
main()
{
int m,n;
printf("enter m and nvalues:");
scanf("%d%d",&m,&n);
printf("gcd (%d , %d) is: %d",m,n,gcd(m,n));
}
int gcd(int m,int n) /* Non-recursive Function */
{
int r;
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return(n);
}

Output:

Example program:

Recursion program to find the product of two numbers

# include<stdio.h>
# include<conio.h>
void main()
{
int prod(int,int);
int a,b,c;
printf("enter a and b:");
scanf("%d%d",&a,&b);
c=prod(a,b);
printf("product=%d",c);
}
int prod(int x,int y)
{
 if((y==0)||(x==0))
 return 0;
 else if(y==1)
 return x;
 else
 return (x+prod(x,y-1));
}

Output: