Являются ли эти два метода вместе формой рекурсии?

Question

Являются ли эти два метода вместе формой рекурсии?

1

У меня есть два метода: первый метод вызывает второй метод из forloop, но второй метод возвращает первый метод с идентификатором поддерева. Является ли это формой рекурсии? Хотя тот же самый метод не вызывает себя, существует ли риск или любых других проблем, которые могут быть связаны с обычными рекурсивными методами?

void AddItems(int id)
{
   var items = GetItems(id);

   foreach (var item in items)
   {
      AddItem(item);
   }
}

void AddItem(Item item)
{
   DoSomething(item);
   AddItems(item.subItemId);
}

EDIT: Есть ли способ сделать это итеративным? Я использую С#.

Prabhu 21 авг. 2014, в 07:35

Источник

1

Да, это рекурсия.
Stewart 21 авг. 2014, в 05:34
0

@Stewart Stewart Есть ли способ сделать это нерекурсивным?
Prabhu 21 авг. 2014, в 05:35
3

Обычно это называется взаимной рекурсией .
Mike Zboray 21 авг. 2014, в 05:36

Показать ещё 1 комментарий

Теги:

c#

java

loops

.net

recursion

5 ответов

Ещё вопросы

@Stewart Stewart Есть ли способ сделать это нерекурсивным?
Обычно это называется взаимной рекурсией .

Alexander Gessler · Answer 1 · 2014-08-21T02-53-00.000Z

Как правило, если он называет себя, прямо или косвенно, на том же или на разных данных это рекурсия.

Если он не является рекурсивным (что это не так), рекурсия подвержена переполнениям стека. В частности, subItemId который совпадает с его родительским идентификатором, приведет к циклу, вызвав SO.

Я отмечаю, что компилятор C # не обнаруживает и не оптимизирует хвостовые рекурсивные алгоритмы, хотя в некоторых случаях это может быть связано с джиттером.

Eric Lippert · Answer 2 · 2014-08-21T03-24-00.000Z

Является ли это формой рекурсии?

Да; это взаимная рекурсия.

Есть ли риск или любых других проблем, которые могут быть связаны с обычными рекурсивными методами?

Да.

Есть ли способ сделать это итеративным?

Да. Все рекурсивные алгоритмы имеют итеративную форму, поэтому это делает. Я отмечаю, что нет требования, чтобы итеративная форма была легко найти или легко понять. Однако в этом случае итеративный алгоритм очень хорошо известен; это глубина первого обхода дерева. Сделайте поиск в Интернете, и вы быстро научитесь использовать явный стек или явную очередь для управления обходами дерева итеративно.

TheLostMind · Answer 3 · 2014-08-21T04-20-00.000Z

Это не прямая рекурсия, потому что рекурсия определяется как метод вызывает себя. Но в вашем случае есть косвенная рекурсия. Итак, да, вы рискуете StackOverFlowError

Dharani Kumar · Answer 4 · 2014-08-21T04-15-00.000Z

да, это довольно просто:

void AddItems(int id) {
    tempID = id;
    bool loop = true;
    while(loop) {
        var items = GetItems(id);
        for each(var item in Items) {
            DoSomething(item);
            id = item.subitemID;
            continue;
        }
        loop = false;
    }
}

Не проверял его. Но должен сделать трюк... Вы также можете взглянуть на инструкцию GOTO http://msdn.microsoft.com/en-IN/library/13940fs2.aspx

Попробуйте проверить это. Этот код неверен.

user3962811 · Answer 5 · 2014-08-21T04-32-00.000Z

Рекурсия происходит, когда функция вызывает себя. В обоих элементах void() s функция вызывает себя. Тем не менее, каждая рекурсивная функция нуждается в базовом случае, или она будет бесконечно возвращаться, что будет иметь место здесь. Сделайте домашнее задание, есть тонны сайтов, объясняющих рекурсию.

Строго говоря, может быть базовый случай, если список подпунктов пуст.
Просто цитирую источники: cprogramming.com/tutorial/c/lesson16.html , не могу найти мою университетскую книгу в цифровом формате, но это в значительной степени стандартное объяснение, используемое в литературе. Да, был бы базовый случай, если список подпунктов пуст.