Блог

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

 struct link 
{
  int value; //data    
  link_t *next; //link
};

struct list
{
    link_t *first;
    link_t *last;
};


int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc   list_size_count((first->next), 1));
  }
  return acc;
}

int linked_list_size(list_t *list)
{
  return list_size_count((list->first),0);
}
 

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

 int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc   list_size_count((first->next), 1));
  }
  return acc;
}
 

Вот как сделать его хвост рекурсивным:

 int list_size_count(link_t *first, int acc)
{
  if(first != NULL)
  {
    return list_size_count(first->next, acc   1);
  }

  return acc;
}
 

Является ли моя функция здесь хвостовой рекурсией?

Нет, это не так.

Эта строка

 return (acc   list_size_count((first->next), 1));
 

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

Но это легко превратить в хвостовую рекурсию. Просто измените приведенную выше строку на:

   acc;
return list_size_count((first->next), acc);
 

Здесь acc сначала увеличивается и передается в качестве аргумента рекурсивной функции, а результат рекурсивного вызова используется непосредственно в операторе return.

Теперь после рекурсивного вызова нет операции. Следовательно, это хвостовая рекурсия.

Если конечным действием процедуры является вызов другой процедуры, это называется завершающим вызовом. Примером может служить процедура, скажем , процедура с именем g , которая заканчивается return f(x); . Самый простой способ скомпилировать этот код -:

• Передайте аргумент x , скопировав его в указанное место для передачи аргумента.
• Выполните команду вызова подпрограммы для вызова f .
• Очистите кадр стека (например, восстановив указатель стека до значения, которое он имел, когда эта процедура начала выполняться) и выполните команду возврата.

Поскольку это последнее, что будет делать рутина g , нам не нужно возвращаться к f этому g . Вместо того, чтобы вызывать его, мы можем перейти к нему:

• Скопируйте x туда, где передается аргумент.
• Выполните команду ветви, к которой нужно перейти f .

Затем f выполнится, очистит кадр стека, в котором мы находимся в данный момент, и выполнит команду возврата. Это вернется к g вызывающему абоненту, как если g бы он выполнил команду возврата. Мы получаем тот же эффект от этих инструкций, что и от предыдущих инструкций, но с меньшим количеством работы.

(Более подробная информация здесь не показана. Чтобы это работало, правила управления фреймами стека должны позволять f очищать фрейм стека g , даже если f он также может создавать свой собственный контекст в стеке.)

Если f и g являются одной и той же процедурой, это называется хвостовой рекурсией.

Обратите внимание, что в этом примере f и g должны возвращать данные одного и того же типа. Если f возвращает a float и g возвращает an int , то, когда g содержит return f(x); , вызов f на самом деле не последнее, что g делает. В операторе есть автоматическое преобразование из float в int return , так что это не будет хвостовым вызовом.

Заключительный вызов просто должен быть последним действием подпрограммы; он не обязательно должен быть последним исходным кодом в подпрограмме. Если return f(x); появляется где-либо в подпрограмме (и типы совпадают), это завершающий вызов, и его можно заменить ветвью (если позволяют правила управления стеком). Кроме того, если возвращаемый тип g является пустым, то f(x); return; в любом месте процедуры выполняется завершающий вызов, а в конце процедуры выполняется завершающий f(x); вызов.

В вашей рутине linked_list_size return list_size_count((list->first),0); есть хвостовой вызов , но это не хвостовая рекурсия.

В вашей подпрограмме list_size_count нет хвостового вызова , потому что in return (acc list_size_count((first->next), 1)); выполняется после вызова to list_size_count . Вы можете сделать его завершающим вызовом и завершающей рекурсией, переписав его в:

 return list_size_count(first->next, acc 1);