Оптимизация рекурсии

@SinAlex · Регистрация: 15.01.2013

Студворк — интернет-сервис помощи студентам

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Fibonacci
{
    public static long f(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return f(n - 1) + f(n - 2);
    }
}
public static void main(String[] args)
{
    int m = 100;
    long[] mas = new long[m];
    for(int n = 0; n < mas.length; n++)
        mas[n] = f[n];
}

Подскажите пожалуйста, как оптимизировать этот кусок кода? Больно уж долго выполняется.

@turbanoff · 08.02.2013, 22:55

Первая оптимизация рекурсии - отказаться от использования рекурсии. Перепишите на один обычный цикл.

@SinAlex · 08.02.2013, 23:04 **[ТС]**

Тут пример заключаться в использовании рекурсии. Поэтому ищу пути оптимизировать именно рекурсию.

@mutagen · 09.02.2013, 01:33

Сообщение от turbanoff

Первая оптимизация рекурсии - отказаться от использования рекурсии. Перепишите на один обычный цикл.

Мы со Скипи проводили тут тесты, ничего такого не надо, JVM сама прекрасно преобразует хвостовую рекурсию в циклы.

https://blogs.oracle.com/jrose... _in_the_vm

интересная статья

@Севак · 09.02.2013, 12:31

Для красоты переписал бы так

Java
1
2
3
public static long f(int x){
        return ((x == 1) || (x == 2))? 1 : (f(x-2) + f(x-1));
    }

@Fonduee · 09.02.2013, 13:18

Время выполнения: 3 ms

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package org.example;
 
import java.math.BigInteger;
import java.util.ArrayList;
 
public class Fibonacci
{
 
    private static ArrayList<BigInteger> fibCache = new ArrayList<BigInteger>();
    static
    {
        fibCache.add(BigInteger.ZERO);
        fibCache.add(BigInteger.ONE);
    }
 
    public static BigInteger fib(int n)
    {
        if (n >= fibCache.size())
        {
            fibCache.add(n, fib(n - 1).add(fib(n - 2)));
        }
        return fibCache.get(n);
    }
 
    public static void main(String[] args)
    {
        long a = System.currentTimeMillis();
        fib(2000);
        System.out.println("Take " + (System.currentTimeMillis() - a) + " ms");
    }
}

@mutagen · 09.02.2013, 16:02

В целом красиво, но если уж городить такой красивый код, то не мешало бы создать кеш в классе, чтобы не пересчитывать каждый раз всю цепочку если к примеру фибоначи требуется считать в цикле, с кешем получится надо будет досчитать только от конца кеша до нужного значения

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@turbanoff 4094 / 3828 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 12
	08.02.2013, 22:55
	Первая оптимизация рекурсии - отказаться от использования рекурсии. Перепишите на один обычный цикл. 0

@SinAlex 0 / 0 / 0 Регистрация: 15.01.2013 Сообщений: 9
	08.02.2013, 23:04 [ТС]
	Тут пример заключаться в использовании рекурсии. Поэтому ищу пути оптимизировать именно рекурсию. 0

@mutagen 2587 / 2260 / 257 Регистрация: 14.09.2011 Сообщений: 5,185 Записей в блоге: 18
	09.02.2013, 16:02
	В целом красиво, но если уж городить такой красивый код, то не мешало бы создать кеш в классе, чтобы не пересчитывать каждый раз всю цепочку если к примеру фибоначи требуется считать в цикле, с кешем получится надо будет досчитать только от конца кеша до нужного значения 0