Это действительно просто общий вопрос CS. Я пытался расширить свои знания об алгоритмах и структурах данных. И, конечно же, в каждом классе CS полно примеров рекурсивных алгоритмов. Кто-нибудь когда-нибудь реализовывал рекурсивный алгоритм в Apex, учитывая, что существует ограничение на максимальную глубину стека? Или итеративный алгоритм почти всегда подходит?

Мне просто любопытно, каков консенсус сообщества.

Заранее спасибо, что нашли время ответить.

0
Brooks Johnson 17 Апр 2020 в 15:10

4 ответа

Рекурсия вероятно приемлема в большинстве случаев, когда вы будете использовать рекурсию в Apex, несмотря на небольшой размер стека, поскольку большинство алгоритмов в конечном итоге будут ограничены запросами кучи, ЦП или SOQL задолго до того, как вы достичь предела глубины стека.

Например, вот простой бит I писал некоторое время назад. Он использует рекурсию для перемещения по узлам XML. Поскольку большинство XML-структур не имеют 1000 уровней вложенности, этот дизайн был вполне приемлем для моего варианта использования.

В качестве альтернативы, используя рекурсию для вычисления чисел Фибоначчи или n! может быть плохой идеей, так как вы будете ограничены только первой 1000 таких номеров. Прежде чем решить использовать рекурсию (или нет), рассмотрите максимально возможную глубину, которую вам нужно пройти. Если кажется маловероятным, что вы когда-нибудь достигнете этого предела, рекурсия, вероятно, приемлема.

Я продолжаю использовать неопределенные термины, такие как «вероятно», потому что есть еще фактор процессора. Вызов методов относительно дорог по сравнению с использованием простого подхода на основе индексов, поэтому глубоко рекурсивные методы могут выиграть от отказа от использования рекурсии. Следует провести некоторые испытания, если вы не уверены.

6
sfdcfox 17 Апр 2020 в 15:26
2
Вы когда-нибудь находили потребность в последовательности Фибоначчи в разработке Salesforce?? Поделись, пожалуйста! ржу не могу
 – 
stackasaur
17 Апр 2020 в 15:31
4
Мне нужно реализовать корпоративный генератор Fizz Buzz;)
 – 
Brooks Johnson
17 Апр 2020 в 15:32
2
Однажды я написал генератор Фибоначчи в Apex. Я думаю, что это был скорее учебный опыт, чем использование в бизнесе. Насколько я помню, именно этот метод познакомил меня с ограничением стека.
 – 
sfdcfox
17 Апр 2020 в 15:43
2
@BrooksJohnson, мне за это недостаточно платят FooBars!
 – 
stackasaur
17 Апр 2020 в 15:51
Что касается этой темы, то именно мой факториальный калькулятор впервые познакомил меня с пределом стека.
 – 
Brooks Johnson
17 Апр 2020 в 16:21

Да, но очень редко.

В Salesforce мне нужно было использовать его только дважды:

  1. При использовании HTTP и преобразовании ответа XML в JSON.
  2. Если вы начнете создавать действительно сложные системы назначения пользователей/пользователей сообщества другим объектам по таким параметрам, как расстояние, вы можете в конечном итоге рекурсивно вызывать метод с увеличивающимся параметром расстояния до тех пор, пока не достигнете максимального расстояния или количества людей, которые вам нужны.

Вы по-прежнему должны следовать тем же ограничениям SOQL, поэтому вам не захочется вызывать метод для родителя, который получает потомков, а затем одно и то же для каждого потомка и так далее, поскольку вы нажмете ограничения. Так что, на мой взгляд, действительно становится трудно найти столько потребностей в Apex.

Также интересно узнать, что говорят другие!

2
stackasaur 17 Апр 2020 в 15:26
1
№ 2 на самом деле похож на вариант использования, для которого мы используем рекурсию. Мы создаем группы обмена динамически по ролям с использованием шаблона регулярных выражений, потому что роли в нашей организации часто меняются, и мы не хотели, чтобы наши администраторы постоянно создавали общедоступные группы.
 – 
sfdcfox
17 Апр 2020 в 15:53
Теперь, не видя подробностей, я бы сказал, что № 2 будет просто использовать Map> для интерактивной реализации.
 – 
Phil W
17 Апр 2020 в 17:03
Я не хочу слишком много говорить о деталях, но проблему можно было смоделировать в виде графа (типа ребер и узлов), и она стала проблемой обхода.
 – 
stackasaur
17 Апр 2020 в 17:25

Кто-нибудь когда-нибудь реализовывал рекурсивный алгоритм в Apex, учитывая, что существует ограничение на максимальную глубину стека?

Я столкнулся с этой ситуацией пару лет назад, когда искал решение для отображения иерархии учетных записей на странице Visualforce. Фактически, я использовал пакет Inline Account Hierarchy от Salesforce Labs, который имеет рекурсивная реализация. Я думаю, что рекурсия все еще может быть применима для некоторых случаев использования, и я не вижу никаких проблем в реализации, если она хорошо реализована в рамках платформы, применимой для любой другой реализации.

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

2
Jayant Das 17 Апр 2020 в 19:29
1
Отличный пример использования, спасибо, что поделились. конечно, помня об ограничениях регулятора, но это классический вариант использования рекурсии... обход дерева глубины N с неизвестной шириной... определенно хорошо решается с помощью рекурсии.
 – 
krigi
17 Апр 2020 в 19:43

Недавно меня попросили придумать решение для такого типа сценария: представьте, что мы находимся в организации, которая использует дела, и есть два настраиваемых десятичных поля: Total_Duration__c (поле формулы) и Family_Total_Duration__c в объекте дела. Напишите метод, который принимает идентификатор "родительского" дела и вычисляет Family_Total_Duration__c для "родительского" дела и всех его дочерних дочерних... дочерних дел как сумму всех сумм Total_Duration__c для дел под ним. Этот тип требования по определению является рекурсивным, и решение включает что-то вроде этого:

Decimal sum(Map<Id,Case> caseMap, Id currentId, Map<Id,Set<Id>> parentIdToChildIds) {
        decimal sum = caseMap.get(currentId).Total_Duration__c;
        if (parentIdToChildIds.containsKey(currentId)) {
            for (Id i : parentIdToChildIds.get(currentId)) {
                sum += sum(caseMap, i, parentIdToChildIds);
            }
        }
        caseMap.get(currentId).Family_Total_Duration__c = sum;
        return sum;
    }

Меня также попросили вычислить модуль строкового представления числа, которое слишком велико для хранения в виде Long. Убрав последние 8 символов и используя распределительное свойство модульного умножения, я смог найти рекурсивное решение, способное выполнить операцию.

1
Mitch Spano 17 Апр 2020 в 20:05