5
  1. Почему поиск чисел Фибоначчи решается с помощью рекурсии? В интернете много примеров с рекурсией - чем простое сложение не нравится?
  2. С рекурсией решается быстрее, если искать до 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);
    }
    
13
  • 1
    Обычно рекурсия с числами Фибоначчи приводится как пример "так делать нельзя!". Вы внимательно читали?
    – Harry
    1 мар 2018 в 6:10
  • @harry во всех примерах в интернете пишут так?), другой вопрос почему в маленьких случаях это быстрее
    – J Mas
    1 мар 2018 в 6:27
  • @regent да, можно оптимизировать, добавив еще одну проверку, но для -1 и -2 вернется 0. добавил теперь рекурсия быстрее до 18 числа
    – J Mas
    1 мар 2018 в 6:43
  • @JMas это не столько оптимизация, сколько часть алгоритма: два элемента (обычно с индексами 0 и 1) зафиксированы, а остальные рассчитываются на их основе.
    – Regent
    1 мар 2018 в 6:48
  • Рекурсия при получении чисел Фибоначчи используется исключительно в главе "Рекурсия для начинающих". Т.е. не для получения чисел, а для объяснения, что есть рекурсия. Почему с рекурсией быстрее Потому что так написана нерекурсивная функция. Сделал бы типа fib[0]=0; fib[1]=1; for(i=2;i<N;i++){fib[i%2]=fib[0]+fib[1];}; return fib[N%2]; - было бы быстрее...
    – Akina
    1 мар 2018 в 7:00

1 ответ 1

6

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

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

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

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

10
  • Подпишите плиз, что у вас в таблице показано, какие столбцы?
    – Kromster
    1 мар 2018 в 7:40
  • По результатам я так понял что нерекурсивный вариант выполняет за 0 микросекунд любое число. Почему так быстро?
    – J Mas
    1 мар 2018 в 7:54
  • 1
    @JMas Так это C, программа выполняется прямо на процессоре. А складывает и перемещает в кеше пару значений процессор оооочень быстро.
    – Mike
    1 мар 2018 в 7:59
  • @mike тогда другой вопрос. почему на С так долго рекурсия идет? так же я не понял тему про С рекурсией не быстрее никогда, вы имели ввиду что с рекурсией всегда долго, почему?
    – J Mas
    1 мар 2018 в 8:01
  • @JMas Думаю в случае с циклом, так как переменных всего 4 (со счетчиком цикла), все операции вообще проходят в регистрах, даже работы с памятью нет (кроме возврата результата). А в случае рекурсии приходится значения сохранять в стеке, делать вызов процедуры. потом еще один if (не известно как предсказатель переходов его отрабатывает и не сбрасывает ли конвеер), плюс в функциях куча лишней работы по подготовке и выходу из функции
    – Mike
    1 мар 2018 в 8:04

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.