Recursion

      Recursive Function is a function calling itself.  

      Every  recursive function should have a base case.Recursion stops on reaching the base case.Without a base case function repeats infinite times.
      Recursion makes the program simpler but it occupies more space and slower than loops.

      Recursive function uses memory stack to store the intermediate values    . Each recursion in the program gets fresh memory allocation. Calculation starts once the base case is reached.

Example:
void sum(int a,int b)
{
-----------;
----------;
sum(a,b);
----------;
}

Example 1: 

Sum of first n natural numbers:

int sum(int n)

{

         if(n<=0) // base case to end recursion

           return 0; // if the given number is 0 then sum is 0

      else

       return(n+sum(n-1));

}

5+ sum(4)

 4+sum (3)

      3+sum (2)

       2+ sum (1)

        1 + sum(0)

         0 

    When the value becomes zero , according to the base case it should return 0. So

 remember it uses stack(Last In First Out)

  1 + sum(0) will be 1+ 0 = 1

  2+ sum (1) will be 2 + (the previous answer which is 1) = 3

 3+sum (2)   will be 3 + (the previous answer which is 3) = 6

 4+sum (3) will be 4 + (the previous answer which is 6) = 10

5+ sum(4)  will be  5 + (the previous answer which is 10) = 15

So the final answer is 15.

Example : 
Find the output [ISC 2017]
int magicfun(int n)
{
    if(n==0)
       return 0;
    else
      return magicfun(n/2)*10+(n%2)
}

find the output if n=7
magicfun(3) *10 + 1
magicfun(1)*10+1
magicfun(0)*10+ 1

so
0 *10 +1 =1
1*10 + 1= 11
11 *10 + 1 =111

A common example  is finding factorial using Recursion.

Here in factorial we are multiplying from 1 till the number given.
Using Loops:

void factorial(int n)
{
int i,f=1;
for(i=1;i<=n;i++)
{
       f=f*i;
 }
System.out.print(f);

Using Recursion :

int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return 1;
   else
         return ( n *(factorial(n-1));  //  multiply the given number with the          
                                                           previous number and so on
}
If n is 5 , then 5 x 4 x 3 x 2 x 1 = 120

This also can be written like this:
int f=1;
int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return f;
   else
         {
               f=f*n;                     // multiply the given number with f which is 1
         return(factorial(n-1));  //  Call the method with the  next number
}
We will do some programs where we use factorial.
Example 1. Permutation function

int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return 1;
   else
         return ( n *(factorial(n-1));  //  multiply the given number with the          
                                                           previous number and so on
}
void permutation()

{
    int x=factorial(n); // Calculate factorial of n
    int  y=factorial(n-r); // Calculate factorial of (n – r)
    int answer= x/y;
    System.out.print(answer);
}
Example 2: Special number / Krishnamurthy number
int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return 1;
   else
         return ( n *(factorial(n-1));  //  multiply the given number with the          
                                                           previous number and so on
}
void special(int n)
{
   int a,s=0,m=n;
   while(n>0)
   {
         a=n%10;
         s=s+factorial(a);
         n=n/10;
    }
if (s==m)
System.out.print(“Special Number”);
else
System.out.print(“Not a Special Number”);

Example 3:
sum

int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return 1;
   else
         return ( n *(factorial(n-1));  //  multiply the given number with the          
                                                           previous number and so on
}

void sum(int  x )

{
int i, a,sum=1;
for(i=1;i<=n;i++)

  sum=sum+(x/ factorial(i));

System.out.print(sum);

}

POWER

To find the power of a number:

Using Loop:
int  p=1;
int powerNum(int  base, int  power)
{
    int ctr=1;
    while(ctr<=power)
{
    p=p*base;
    ctr++;
 }
  return p;
 }

Using Recursion:
int powerNum(int  base, int  power)
{
   if (power==0)  // whatever the  base ,if  the power is  0 then answer is 1

        return 1;
   else
       return(base * powerNum(base, power-1));
}
Example 1:
Sum

Here  both factorial and power  can be calculated using recursion technique.

int factorial(int n)
{
   if (n==0)                //   factorial of 0 is 1
         return 1;
   else
         return ( n *(factorial(n-1));  //  multiply the given number with the          
                                                           previous number and so on
}

int powerNum(int  base, int  power)
{
   if (power==0)  // whatever the  base ,if  the power is  0 then answer is 1

        return 1;
   else
       return(base * powerNum(base, power-1));
}
void series(int x,int n)

{

int i;
double s=0.0;
for(i=1;i<=n;i++)
s=s+powerNum(x,i)/factorial(i);
System.out.print(s);
}

Fibonacci Series
0,1,1,2,3,5,8...........
void Fibonacci(int n)
{
    int ctr=3,a=0,b=1,c=0;
while (ctr<=n)
{
  c=a+b; // add the previous two values
  System.out.print(c+”  “);
  a=b;   
  b=c;
  ctr++;
}
}
    

int Fibonacci(int n) //to find the nth term in Fibonacci series

{

if (n==1)
return 0;
if (n==2)
return 1;
else
return (Fibonacci(n-1)+Fibonacci(n-2));
}

Prime Number

int c=0;
int Prime(int n, int i)
{
  if(i<=n)
  {
        if(n%i==0)
           c=c+1;
           return (Prime(n,i+1));
}
else
          return c;
}

Try the following:

·        Twin Prime