Geek asks and answers

Recursive function and non-recursive function returning different results

I create two functions that should emulate and return the result f (i) = 1/1 + 1/2 + 1/3 ... 1 / i. One function is recursive, and I verify that the recursive function is functioning correctly by implementing the non-recursive version. However, I found that both functions return similar answers that are not quite the same. Can someone explain why functions return different values?

When I run the functions in the main method of the class to which they belong, I get the following output:
Recursive for 1000: 7.4854784
Not recursive for 1000: 7.4854717
Recursive
for 1: 1.0
Recursive for 1: 1.0 Recursive for 483: 6.758268 Not
recursive for 483: 6.758267

Here is my code:

static float RecursiveFunction(int num){
    //The num parameter represents the denominator that will be used
    //The recursive function is continually called at lower increments of num

    //If num is one, return 1 and do not call RecursiveFunction again
    if (num == 1) {
        return 1;
    }
    //Otherwise, return 1/num (in floating point decimal) and call RecursiveFunction with a parameter of num - 1
    else {
        return 1/(float)num + RecursiveFunction(num - 1);
    }
}

//A Non-recursive version of RecursiveFunction that will be used to test RecursiveFunction
static float NonRecursiveFunction(int num) {
    //The total variable adds up the fractions
    float total = 0;
    //While num is greater than zero, add 1/num to total and then subtract 1 from num
    while (num > 0) {
        total += 1/(float)num;
        num -= 1;
    }
    return total;
}
+3
source share
3 answers

This is due to rounding errors from using a data type floatthat is a 32-bit IEEE 754 with one floating point precision . When a number requires more precision than a data type can handle it, it will be rounded - this will happen when you add a few floats together.

float BigDecimal, :

import java.math.BigDecimal;
import java.math.RoundingMode;

public class RoundingErrors {
    private static final BigDecimal ONE = new BigDecimal( 1 );

    static BigDecimal RecursiveFunction(int num){
        //The num parameter represents the denominator that will be used
        //The recursive function is continually called at lower increments of num

        //If num is one, return 1 and do not call RecursiveFunction again
        if (num == 1) {
            return ONE;
        }
        //Otherwise, return 1/num (in floating point decimal) and call RecursiveFunction with a parameter of num - 1
        else {
            return ONE.divide( new BigDecimal( num ), 100, RoundingMode.CEILING ).add( RecursiveFunction(num - 1) );
        }
    }

    //A Non-recursive version of RecursiveFunction that will be used to test RecursiveFunction
    static BigDecimal NonRecursiveFunction(int num) {
        //The total variable adds up the fractions
        BigDecimal total = new BigDecimal( 0 );
        //While num is greater than zero, add 1/num to total and then subtract 1 from num
        while (num > 0) {
            total = total.add( ONE.divide( new BigDecimal( num ), 100, RoundingMode.CEILING ) );
            num -= 1;
        }
        return total;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println( RecursiveFunction( 1000 ));
        System.out.println( NonRecursiveFunction( 1000 ));
    }
}


7.4854708605503449126565182043339001765216791697088036657736267499576993491652024409599344374118451321
7.4854708605503449126565182043339001765216791697088036657736267499576993491652024409599344374118451321
+3

, , - . :

1/1 + (1/2 + (1/3 + (1/4 + (1/5 + (1/6 + 1/7)))))

:

((((((1/1 + 1/2) + 1/3) + 1/4) + 1/5) + 1/6) + 1/7)

, . ? 0. , (, ), . 1.5, . , " " 0 . , .

: http://ideone.com/4Eqduh. :

Rec:             7.4854784
Flat0:           7.4854717
Flat1:           7.4854784
MT0 BigDecimal:  7.4854708605503449126

MT0, , Flat0 ( ) .

0

You can look at http://en.wikipedia.org/wiki/Harmonic_number , I'm not a mathematician, so I only understood that, but it can provide a way for you to avoid recursion / loop all together.

0
source

More articles:


All Articles