Рекурсивная функция и нерекурсивная функция, возвращающая разные результаты

Question

Я создаю две функции, которые должны эмулировать и возвращать результат f (i) = 1/1 + 1/2 + 1/3 ... 1/я. Одна функция рекурсивна, и я проверяю, что рекурсивная функция функционирует правильно, реализуя нерекурсивную версию. Тем не менее, я обнаружил, что обе функции возвращают похожие ответы, которые не совсем то же самое. Может кто-нибудь объяснить, почему функции возвращают разные значения?

При запуске функции в основном методе класса, к которому они принадлежат, я получаю следующий вывод:
Рекурсивных за 1000: 7,485478 нерекурсивен за 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, который является single-precision 32-bit IEEE 754 floating point. Когда число требует большей точности, чем тип данных может справиться с ним, он будет округлен - это произойдет, когда вы добавите несколько поплавков вместе.

Если конвертировать 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, я не математик, поэтому я только это понял, но это может помочь вам избежать рекурсии/петли все вместе.