Избегайте рекурсии

Question

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

Текущий код выглядит примерно так:

void Parse(Foo foo)
{
  A()
  for (;;)
  {
    B();
    if (C())
      return;
    if (D())
    {
      Run();
    }
    E();
  }
}

void Run()
{
  X();
  if (Y())
  {
    Parse();
  }
  Z();
}

Выше приведен псевдокод. Буквы A, B, C, D, E, X, Y и Z являются методами, а также Parse () и Run (). Для простоты я пропустил различные параметры и разыменования объектов (например, Run - это метод экземпляра объекта, и он принимает некоторые параметры).

В любом случае, мой вопрос: как мне превратить это в нерекурсивный код?

Мне кажется, что эквивалентный нерекурсивный код:

void Parse(Foo foo)
{
  //create a local stack variable to emulate recursion
  Stack<Foo> foos = new Stack<Foo>();
  foos.Add(foo());
start_subroutine:
  A()
  for (;;)
  {
    B();
    if (C())
    {
      //instead of returning from a recursive call
      if (foos.Count > 1)
      {
        foo = foos.Pop();
        goto end_subroutine;
      }
      return;
    }
    if (D())
    {
      //instead of invoking Run as a subroutine, bring its functionality inline
      //Run();
      X();
      if (Y())
      {
        //instead of calling self recursively
        //Parse();
        //push onto a local stack variable and jump
        foos.Add(foo);
        goto start_subroutine;
      }
end_subroutine:
      Z();
    }
    E();
  }
}

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

Answer 1

Я не могу проверить это, но мне кажется, что вы можете заменить goto start_subroutine на

A();
continue;

и goto end_subroutine с

Z();
E();
continue;

Я не уверен, правда ли это намного лучше :) 1009 *

Answer 2

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

Если вы аккуратно структурируете его и большую часть своего кода реализации используете в других функциях, это выглядит вполне разумным. Тем более что вы используете нерекурсивный код для профилирования:)

Удачи, но в итоге вы продолжаете!