Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
 Подскажите как в цикле или не используя цикл  [new]
x17.mstu
Member

Откуда:
Сообщений: 312
Подскажите как в цикле или не используя цикл или через рекурсию
Не до конца понимаю как сделать через рекурсию чтобы на каждом шаге i запоминалось предыдущее состояние
создать строку, состоящую из чисел от 0 до 20000. Важно понимать, что это одна строка, полученная конкатенацией (“склеиванием”) чисел из диапазона через пробел (0 + “ “ + 1 + “ “ + 2 + … + 20000).
3 ноя 20, 22:22    [22226020]     Ответить | Цитировать Сообщить модератору
 Re: Подскажите как в цикле или не используя цикл  [new]
mayton
Member

Откуда: loopback
Сообщений: 49763
Тут не получается красивое решение на рекурсии в духе ФП.

Java не поддерживает хвостовую рекурсию. Тоесть она по настоящему будет использовать стек.
И надо обеспечить 20 тысяч уровней вложенности. Это опасно по причине Stackoverflow.
Возможно придется для этой задачи менять
$ java -Xss ....

Но вдвойне опасно то что на каждом уровне стека мы будем передавать растущую иммутабельную строку
которая также создаст проблемы для другой памяти типа Heap с квадратичным ростом потребления.
Это можно слегка придавить если передавать строку в передаваемый StringBuilder но это
как говорил Шипилёв - "калечить" код в угоду перформансу.

Вобщем я советую забыть вообще про рекурсию и делать циклом.

Сообщение было отредактировано: 3 ноя 20, 22:53
3 ноя 20, 22:57    [22226042]     Ответить | Цитировать Сообщить модератору
 Re: Подскажите как в цикле или не используя цикл  [new]
vsl
Member

Откуда:
Сообщений: 46
x17.mstu,
public class R {

    public static void main(String[] args) {
        System.out.println(numbers(Integer.parseInt(args[0]), Integer.parseInt(args[1])));
    }

    private static String numbers(int a, int b) {
        if (a >= b) return String.valueOf(a);
        int c = (a + b) / 2;
        return numbers(a, c) + " " + numbers(c + 1, b);
    }
}


java R 0 20000
4 ноя 20, 00:32    [22226074]     Ответить | Цитировать Сообщить модератору
 Re: Подскажите как в цикле или не используя цикл  [new]
mayton
Member

Откуда: loopback
Сообщений: 49763
Хм... делить пополам. Тоже интересно.
4 ноя 20, 00:38    [22226077]     Ответить | Цитировать Сообщить модератору
 Re: Подскажите как в цикле или не используя цикл  [new]
mayton
Member

Откуда: loopback
Сообщений: 49763
Напомнило оптимизацию Фибоначчи из SICP
4 ноя 20, 14:45    [22226252]     Ответить | Цитировать Сообщить модератору
Все форумы / Java Ответить