CODEWITHSUNDEEP
javarecursionfractions
user3025042
user3025042

Reputation: 11

adding fractions using recursion e=1+1/1!+1/2!+1/3!+

I need to write a recursive method to compute the following series: e = 1+1/1!+1/2!+1/3!+...

This is what I have so far.

public static void main(String[] args)
{  System.out.println("enter n :");
   int n =scan.nextInt();
   double h = fact(n);
   System.out.println(" e = ");
}
public double fact(int n)
 {
    if (n == 1)
        return 1;
    else
        return ???;
  }
}

Upvotes: 1

Views: 3996

Answers (4)

Ahmed Maher
Ahmed Maher

Reputation: 11

write the code as below and call it from main class.

public static double recursiveFun(double value){
        if (value==1)
            return 1.0;


        if (value==2){

            return (1/(value-1) + 1/value);

        }

        else
            return recursiveFun(value-1) + 1/value;

    }

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533890

Calculating e^n recursively is very expensive. It is O(n^2) and it is hard to know when to stop. Instead I suggest you do it iteratively.

static final int runs = 20000;
static volatile int exp = 1;
static volatile int n = 18;
static volatile double dontOptimiseAway;

public static void main(String[] args) throws InterruptedException {
    System.out.println("Math.exp(1)=" + Math.exp(1));
    System.out.println("exp_iter(18)=" + exp_iter(18));
    System.out.println("exp_recurse(18)=" + exp_recurse(18));

    for (int t = 0; t < 3; t++) {
        System.out.printf("exp(1), exp_iter(18), exp_recurse(18) took %,d / %,d / %,d ns on average%n",
                timeMathExp(), timeExpIter(), timeExpRecurse());
    }
}

public static long timeMathExp() {
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++)
        dontOptimiseAway = Math.exp(exp);
    return (System.nanoTime() - start) / runs;
}

public static long timeExpIter() {
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++)
        dontOptimiseAway = exp_iter(n);
    return (System.nanoTime() - start) / runs;
}

public static long timeExpRecurse() {
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++)
        dontOptimiseAway = exp_recurse(n);
    return (System.nanoTime() - start) / runs;
}

public static double exp_iter(int n) {
    double exp = 0, x = 1;
    for (int i = 2; i <= n; i++)
        exp += (x /= i);
    return 2 + exp;
}

public static double exp_recurse(int n) {
    return n <= 0 ? 1 : 1.0 / fact(n) + exp_recurse(n - 1);
}

public static double fact(int n) {
    return n <= 1 ? 1 : n * fact(n - 1);
}

prints

Math.exp(1)=2.718281828459045
exp_iter(18)=2.718281828459045
exp_recurse(18)=2.7182818284590455
exp(1), exp_iter(18), exp_recurse(18) took 111 / 191 / 760 ns on average
exp(1), exp_iter(18), exp_recurse(18) took 75 / 78 / 558 ns on average
exp(1), exp_iter(18), exp_recurse(18) took 69 / 66 / 552 ns on average

Upvotes: 0

nhgrif
nhgrif

Reputation: 62072

So, assuming the n input you're taking is the starting denominator for the smallest fraction you'd add...

(For example, given n = 10, you want to add 1 through 1/10)

Then you need to set up your method so that when you call fact(10), it's going to return the sum of 1/10 plus the result of fact(9), or more generically, 1/n + fact(1/n-1);

So, you're looking for something like this:

public double fact(int n) {
    if (n < 0) {
        return 0.0;
    } else if (n == 0) {
        return 1.0;
    } else {
        return (1.0/n + fact(n-1))
    }
}

Also, please note the changes to the base cases. When n < 0, we just return 0.0, because if I recall correctly, the factorial of any negative number is always 0, right?

Meanwhile, the base case should be n==0, not n == 1. Your series starts with 1 + 1/1. Note that 1 is not 1/0 or 1/nothing, it's just 1/1. We can't return 1/n when n is 0. For the series to calculate correctly, we have to add the first return the first element of the series in the case of n = 0.

And keep in mind, as with all recursive functions, very large values of n will cause a stack overflow.

Upvotes: 3

Woot4Moo
Woot4Moo

Reputation: 24336

Here are a couple of resources:

Math is fun

"Yes you can! But you need to get into a subject called the "Gamma Function", which is beyond this simple page.

Half Factorial

But I can tell you the factorial of half (½) is half of the square root of pi = (½)√π, and so some "half-integer" factorials are:"

More specifically you want the Gamma Function

Apache commons has an implementation of this function.

Discussion on Math Exchange

And here is an implementation from Princeton

public class Gamma {

   static double logGamma(double x) {
      double tmp = (x - 0.5) * Math.log(x + 4.5) - (x + 4.5);
      double ser = 1.0 + 76.18009173    / (x + 0)   - 86.50532033    / (x + 1)
                       + 24.01409822    / (x + 2)   -  1.231739516   / (x + 3)
                       +  0.00120858003 / (x + 4)   -  0.00000536382 / (x + 5);
      return tmp + Math.log(ser * Math.sqrt(2 * Math.PI));
   }
   static double gamma(double x) { return Math.exp(logGamma(x)); }

   public static void main(String[] args) { 
      double x = Double.parseDouble(args[0]);
      System.out.println("Gamma(" + x + ") = " + gamma(x));
      System.out.println("log Gamma(" + x + ") = " + logGamma(x));
   }

}

Upvotes: 0

Related Questions