Как эта рекурсивная функция автоматически преобразуется в итеративную функцию? - PullRequest
Новая
       7

Как эта рекурсивная функция автоматически преобразуется в итеративную функцию?

4 голосов
/ 29 августа 2011

Я читаю хвостовую рекурсию, как показано ниже

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

Например, 

void print(Iterator start, Iterator end, ostream& out=cout) {
  if(start == end)
      return;
  out << *start++ << endl;
  print(start, end, out);
}

преобразуется в итеративный по вышеуказанной спецификации как 

void print(Iterator start, Iterator end, ostream& out=cout) {
   while(true) {
      if(start == end)
          return;
      out << *start++ << endl;
    }
}

В вышеприведенном отрывке упоминается, что «замена рекурсивного вызова одним присваиванием на аргумент функции, но в данном примере у нас не было никакого присваивания?

Может ли кто-нибудь объяснить и привести пример для приведенного выше объяснения о том, как преобразовать рекурсивную функцию в итеративную функцию?

Ответы [ 5 ]

7 голосов
/ 29 августа 2011

Назначение скрыто в операторе приращения: 

start++;

фактически является присвоением: 

start = start+1;

На самом деле, пример (часть первая) не очень хорош.

out << *start++ << endl;
print(start, end, out);

должно быть 

out << *start << endl;
print( start+1, end, out);
6 голосов
/ 29 августа 2011

Не думаю, что какой-то отрывок, на который вы ссылаетесь, важен; просто сконцентрируйтесь на основной проблеме, где вы хотите преобразовать рекурсивную функцию в обычную итеративную функцию, что можно сделать (без усилий) как 

void print(Iterator start, Iterator end, ostream& out=cout) {
   while(start != end) {
      out << *start++ << endl;
    }
}
1 голос
/ 29 августа 2011

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

На самом деле, если все сделано точно, итерационная функция должна выглядеть следующим образом: 

void print(Iterator start, Iterator end, ostream& out=cout) {
    while(true) {
        if(start == end)
            return;
        out << *start++ << endl;

        start = start;
        end = end;
        out = out;
    }
}

Но этиназначения совершенно не нужны, даже если они правильны.

1 голос
/ 29 августа 2011

Это немного скрыто в C ++, но start++ присваивает новое значение каждому разу в цикле.

0 голосов
/ 29 августа 2011

Общее преобразование рекурсивного в итеративное выглядит следующим образом.

Исходный код: 

void print(Iterator start, Iterator end, ostream& out=cout) {
  if(start == end)
      return;
  out << *start++ << endl;
  print(start, end, out);
}

Преобразованный код: 

void print(Iterator start, Iterator end, ostream& out=cout) {
  while(true) {
     if(start == end)
        return;
     out << *start << endl;

     // One assignment per function argument for 'general' tail recursion
     start = start + 1;       // (1)
     end = end;               // (2)
     out = out;               // (3)
  }
}

Три назначения, как вобъяснение включены.Задание (1) встроено в start++, назначения (2) и (3) оптимизированы.

...