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

#java #алгоритм #задание_на_собеседовании

Почему поиск чисел Фибоначчи решается с помощью рекурсии? В интернете много примеров
с рекурсией - чем простое сложение не нравится?
С рекурсией решается быстрее, если искать до 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);
}


    

Ответы

Ответ 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