Вопрос:

Шаблонные методы C ++ для исправления рекурсии?

c++ templates recursion design-patterns

67 просмотра

1 ответ

359 Репутация автора

Предположим, у меня есть функция с естественной рекурсией, но я хочу избежать рекурсии по ряду причин. Существуют ли какие-либо хорошие способы применения шаблонов в C ++ для систематического изменения формы выполнения кода, чтобы избежать возможных рисков рекурсии?


В качестве примера, мы можем предположить T1, T2некоторые типы и start(), end()некоторые произвольные функции , принимающие аргументы и возвращающиеся вещи соответствующих типов:

T2 recursion(T1 a1){
  T1 l1 = start(a1);
  if( recurse_condition(a1,l1) )
     T2 l2 = recursion(l1);
  else return final(a1,l1);
  return end(l2);
}

Поэтому, если я правильно понимаю хвостовую рекурсию, это можно будет сделать, только если end()функция ничего не делает, но мы предполагаем, что она может что-то делать.


(Я не очень часто бываю на этом сайте, поэтому не стесняйтесь перенаправлять меня, если вопрос больше подходит где-то еще.)

Автор: mathreadler Источник Размещён: 08.11.2017 10:08

Ответы (1)


1 плюс

46353 Репутация автора

Учитывая ваш пример (немного исправлено)

template <typename T2, typename T1>
T2 recursion(T1 a1){
  T1 l1 = start(a1);
  if( recurse_condition(a1,l1) )
     T2 l2 = recursion<T2>(l1);
  else return final(a1,l1);
  return end(l2);
}

Я полагаю, вы можете избежать рекурсии с чем-то вроде (также C ++ 98)

template <typename T2, typename T1>
T2 noRecursion (T1 a1)
 {
   std::size_t cnt ( 0U ); // counter: how many time is
                           // executed `start()`

   T1 l1 ( a1 );

   do
    {
      a1 = l1;
      l1 = start(a1);

      ++cnt;
    }
   while ( recurse_condition(a1, l1) );

   T2 l2 ( final(a1, l1) );

   // exec end() one time less than start()
   while ( --cnt ) // shorter than for (auto ui = 1U ; ui < cnt ; ++ui)
      l2 = end(l2);

   return l2;
 }

В этом случае аспект шаблона ( T1и T2) не зависит от аспекта рекурсии / нерекурсии: полезен в нерекурсивной функции, если полезен в рекурсивной версии.

Автор: max66 Размещён: 08.11.2017 10:45
Вопросы из категории :
32x32