Recursion in Java example

What is Recursion?

Recursion is a programming technique in which a method calls itself.This may sound like a strange thing to do or even a catastrophic mistakes.
Recursion is however, one of the most interesting and one of the most surprising effective techniques in programming.we will discuss the strength and weakness of recursion and show how a recursion approach can be transformed into a stack-based approach.

Triangular Numbers:

A band of mathematicians in ancient Greece who worked under Pythagoras and felt a connection with the series of numbers 1,3,6,10,15,21,........
Can you find the next member of this series?

The nth term in the series is obtained by adding n to the previous term.thus second term is found by adding 2 to the first term(which is 1),giving 3.The third term is 3 added to the second term(which is 3) giving 6, and so on.The numbers in the series are called Triangular Numbers.


Finding the nth Term Using a Loop:

int traingle(int n)
{
  int total=0;

while(n>0)
 {
    total=total+n;
    --n;
 }

  return total;
}

The method cycles around the loop n times,adding n to total the first time,n-1 the 2nd time and so on down to 1,quitting  the loop when n becomes 0 .


Finding the nth Term Using Recursion:

1. The first column,which has the value n.
2. The sum of all the remaining columns.

Code implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class TraingleApp
{
   static int theNumber;

public static void main(String[] args) throws IOException
{
System.out.println("Enter a number:");
        theNumber=getInt();    
        int answer=traingle(theNumber);
        System.out.println("Traingle=" +answer);
}

public static int traingle(int n)
{
if(n==1)
return 1;
else
return (n+traingle(n-1));
}

private static int getInt() throws IOException
{
String s=getString();
return Integer.parseInt(s);
}


private static String getString() throws IOException
{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}

}


Characteristics of Recursive Methods:

• It calls itself.
• When  it calls itself,it does so to solve a smaller problem.
• there is some version of the problem that is simple enough that the routine can solve it and return ,without calling itself.

Is Recursion Efficient:

Calling a method involves certain overhead such as Memory but it can be controlled control must be transferred from the location of the call to the beginning of the method.

In the case of traingle() method its probable that as a result of the overhead, the while loop approach executes  more quickly than the recursive approach.

Recursion is usually used because it simplifies a problem conceptually not because it is inherently more efficient.

Factorial Example in Recursion:

int factorial(int n)
{
  if(n==0)
   {
       return 1;
   }

   else
    {
      return (n * factorial(n-1));

    }
}