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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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