递归函数和非递归函数返回不同的结果

Question

我正在创建两个函数，它们应该模拟并返回 f（i） = 1/1 + 1/2 + 1/3 ...1/i.一个函数是递归的，我正在通过实现递归函数的非递归版本来测试递归函数是否正常运行。但是，我发现这两个函数返回的答案并不完全相同。 有人可以解释为什么函数返回不同的值吗？

当我在它们所属的类的 main 方法中运行函数时，我得到以下输出：
1000 的递归：7.4854784
1000 的非递归：7.4854717
递归 1：1.0
1：1.0
的非递归483 的递归：6.758268
483 的非递归：6.758267

这是我的代码：

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;
}

Answer 1

这是

由于使用 float 数据类型（单精度 32 位 IEEE 754 浮点）时的舍入误差。当数字需要的精度高于数据类型可以处理的精度时，它将四舍五入 - 当您将多个浮点数相加时，就会发生这种情况。

如果将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

Answer 2

我能想到的唯一原因是因为它们加在一起的顺序。非递归函数执行以下操作：

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 函数（首先对小数字求和）是最准确的。

Answer 3

你可能

想看看 http://en.wikipedia.org/wiki/Harmonic_number，我不是数学家，所以我只是有点理解它，但它可能会为你提供一种避免递归/循环的方法。