Являются ли простые хвостовые рекурсивные функции эффективными, как петли?

Иногда я нахожу, что пишу хвостовые рекурсивные функции. Я искал высоко и низко, и я обнаружил, что в платформе .NET есть хвостовая рекурсия, но я не уверен, в каких случаях я могу, и в каких случаях я не могу эффективно использовать рекурсию хвоста. Например, у меня есть простое дерево, назовем его

public class Tree
{
  public Tree parent = null;

  public Tree(Tree parent)
  {
    this.parent = parent;
    this.children = new List<Tree>();
  }

  public List<Tree> children {get; private set;}

  public Tree root
  {
    get
    {
      return this.parent == null ? this : parent.root;
    }
  }
}

для свойства root, будет ли компилятор испускать цикл? он испустит .tail? Будет ли дрожание уважать .tail? ничего не случится, и будет ли алгоритм просто рекурсивно работать? Самое главное, следует ли переписать это как итеративный?

Ответы

Ответ 1

Компилятор С# никогда не будет использовать префикс tail.

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

В вашем коде нет ничего в положении хвоста. Причина заключается в использовании тройного оператора. Если код переписан для использования операторов if с возвратом каждой ветки, то вызов parent.root будет находиться в хвостовом положении.

В плане оптимизации компилятор (F # или IronScheme) обычно преобразует хвостовые рекурсивные вызовы в циклы while (true) { ... }. Это делается, поскольку он удаляет как хвостовой вызов, так и необходимость повторного вызова метода.

Поэтому, если С# было разрешено испускать хвостовые вызовы (что это не так), это, скорее всего, будет преобразовано из:

public Tree root
{
  get
  {
    if (parent == null) return this;
    else return parent.root; // now in tail position
  }
}

(только гость)

public Tree root
{
  get
  {
    Tree temp = this;
    while (true)
    {
      if (temp.parent == null)
      {
         return temp;
      }
      temp = temp.parent;
    }
  }
}

F # и IronScheme выполняют одно и то же преобразование. Это называется tail call elimination (TCE). И да, это будет немного быстрее, чем версия С#. (Я проверил это с помощью microbenchmarking fib на С#, F # и IronScheme)

Ответ 2

Существует аналогичный ответ другого ответа.

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