Что лучше при поиске чисел Фибоначчи - рекурсия или простое сложение?

204

02 марта 2018, 16:52

Почему поиск чисел Фибоначчи решается с помощью рекурсии? В интернете много примеров с рекурсией - чем простое сложение не нравится?

С рекурсией решается быстрее, если искать до 21 числа, а вот все что больше уже намного быстрее решается простым сложением. Почему с рекурсией быстрее, ведь это получается больше почти 100 раз вызов самого себя?

public static void main(String[] args) {
    long l = System.nanoTime();
    long findFib = 16;
    System.out.println("not recursion = " + fib(findFib));
    l = System.nanoTime() - l;
    System.out.println("time = " + l);
    l = System.nanoTime();
    System.out.println("recursion =    " + recFib(findFib));
    l = System.nanoTime() - l;
    System.out.println("time = " + l);
}
private static long fib(long i) {
   long curr = 1;
   long previous = 0;
   for (long j = 0; j < i - 1; j++) {
       long temp = curr;
       curr += previous;
       previous = temp;
   }
   return curr;
}
private static long recFib(long i) {
    if (i < 2) {
        return i;
    }
    return recFib(i - 1) + recFib(i - 2);
}

Answer 1

Ваши два вопроса построены одинаково - спрашивается, почему о неверных вещах. Потому что это на самом деле не так.

В дидактических целях, чтобы показать, что такое рекурсия. Чтобы показать, что неразумное применение рекурсии ведет к неработоспособной программе.
С рекурсией не быстрее никогда - по крайней мере для чисел Фибоначчи и без мемоизации.

Сравнение вот таких функций

long long fibR(unsigned int N)
{
    if (N < 2) return 1;
    return fibR(N-1) + fibR(N-2);
}
long long fibI(unsigned int N)
{
    if (N < 2) return 1;
    long long f0 = 1, f1 = 1;
    for(unsigned int i = 2; i <= N; ++i)
    {
        long long f = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    return f1;
}

на моей машине дает (ссылка на полный код ниже; простите, я на C++ работаю, но не думаю, что на Java что-то изменится :))

N(i) =   3         3         0 mks
N(r) =   3         3         1 mks
N(i) =   6        13         0 mks
N(r) =   6        13         5 mks
N(i) =   9        55         0 mks
N(r) =   9        55        22 mks
N(i) =  12       233         0 mks
N(r) =  12       233        95 mks
N(i) =  15       987         0 mks
N(r) =  15       987       406 mks
N(i) =  18      4181         0 mks
N(r) =  18      4181      1718 mks
N(i) =  21     17711         0 mks
N(r) =  21     17711      7301 mks
N(i) =  24     75025         0 mks
N(r) =  24     75025     24896 mks
N(i) =  27    317811         0 mks
N(r) =  27    317811     86819 mks
N(i) =  30   1346269         0 mks
N(r) =  30   1346269    370024 mks
N(i) =  33   5702887         0 mks
N(r) =  33   5702887   1568399 mks

Примерно тот же результат получается и тут: https://ideone.com/rfjifS