Wednesday, May 27, 2015

Quick Recursive Example

This class can be used to drive the example classes below

public class Driver{
    public static void main(String argv[]){
        Factorial value=new Factorial(4);
        System.out.println(value.getValue());
        Fibonacci value2=new Fibonacci(10);
        System.out.println(value2.getValue());
    }
}

Since factorial(1) is 1, we can use that as a stop value to end the recursive process.  Thus, you need to trace the process by hand on a piece of paper before reading the code below of designing your own algorithm. 

          Factorial(4) = Factorial(4)*Factorial(3)*Factorial(2)*Factorial(1)
          Factorial(1) = 1
          Factorial(2) = 2*Factorial(1) = 2* 1 = 2
          Factorial(3) = 3* Factorial(2) = 3* 2 = 6
          Factorial(4) = 4 * Factorial(3) = 4 * 6 = 24

So, you should see the pattern of factorial(n) is equal to n * factorial(n-1) where factorial(1) will provide the stop operation.

public class Factorial{
  private int x;

  public Factorial(int x){this.x = calculate(x);}

  public int calculate(int value){ return (value == 1 )? 1 : value * calculate(value-1);}
   
  public int getValue(){ return x; }
}

Paper is the key here as well.  Ask a question about the actual sequence of fibonacci numbers and write them down.

0,1,1,2,3,5,8,13,21,34,55,89 for n values 1 - 12.  You can see that we will add the previous two values together in order to find the new value.  Thus, the first two values must be considered as the stop values for the recursive process.  So, if n = 1 then return 0 and if n=2 then return 1.  Anything above the value 2 for n can be recursively calculated y previous two values. 

  Fibonacci(4) = 
  Fibonacci(1) = 0
  Fibonacci(2) = 1
  Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 0 + 1 = 1
  Fibonacci(4) = Fibonacci(3) + Fibonacci(2) = 1 + 1 = 2

Thus, the algorithm emerges.

public class Fibonacci{
    private int x;

    public Fibonacci(int x){this.x = calculate(x);}

    public int calculate(int y){return (y ==1)? 0:(y==2)? 1 : calculate(y-1)+calculate(y-2);}
   
    public int getValue(){return x;}
}

No comments:

Post a Comment