Как распознать, что есть, а что нет хвостовой рекурсии?

Question

Иногда это достаточно просто (если self-вызов является последним утверждением, это хвостовая рекурсия), но все же есть случаи, которые меня смущают.Профессор сказал мне, что «если после самостоятельного вызова нет инструкции для выполнения, это хвостовая рекурсия».Как насчет этих примеров (не обращая внимания на тот факт, что они не имеют особого смысла):

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

function foo(n)
{
    if(n == 0)
        return 0;
    else
        return foo(n-2);
}

б) Но как насчет этого?Это должен быть хвостовой вызов, потому что если условие истинно, ничего, кроме его, не будет выполнено, но это не последний оператор?

function foo(n)
{
    if(n != 0)
        return foo(n-2);
    else
        return 0;
}

c) Как насчет этого?В обоих случаях последний вызов будет выполнен последним:

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}

Answer 1

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

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

Для хвостового вызова вызывающая сторона не делает этого.Он игнорирует любые значения регистров, потому что знает, что они не понадобятся позже.Он устанавливает указатель стека так, что вызываемый будет использовать тот же стек, что и вызывающий, и он не устанавливает себя в качестве адреса возврата, он просто переходит на целевой адрес.Таким образом, вызываемый объект перезапишет ту же область стека, он поместит свое возвращаемое значение в то же место, в котором вызывающий объект поместил бы свое возвращаемое значение, и когда он вернется, он не вернется к своему вызывающему, но вернет к своему вызывающему.caller.

Следовательно, неофициально, функция является хвостовой рекурсивной, когда возможна оптимизация хвостового вызова, и когда целью хвостового вызова является сама функция.Эффект более или менее такой же, как если бы функция содержала цикл, и вместо вызова самого себя, вызов tail переходит к началу цикла.Это означает, что не должно быть никаких переменных, необходимых после вызова (и, действительно, никакой «работы для выполнения», что в языке, подобном C ++, означает, что ничего не должно быть уничтожено), и вызывающее лицо должно вернуть возвращаемое значение хвостового вызова.

Это все для простой / тривиальной хвостовой рекурсии.Существуют преобразования, которые можно использовать для создания чего-то хвостового рекурсивного, чего еще нет, например, для введения дополнительных параметров, которые хранят некоторую информацию, используемую «самым нижним» уровнем рекурсии, для выполнения работы, которая в противном случае была бы выполнена навыход".Так, например:

int triangle(int n) {
    if (n == 0) return 0;
    return n + triangle(n-1);
}

может быть сделан хвост-рекурсивным, либо программистом, либо автоматически с помощью достаточно умного компилятора, например:

int triangle(int n, int accumulator = 0) {
    if (n == 0) return accumulator;
    return triangle(n-1, accumulator + n);
}

Следовательно, прежняя функция можетбыть описанным как "хвостовая рекурсия" кем-то, кто говорит о достаточно умном языке / компиляторе.Будьте готовы к этому варианту использования.

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

Answer 2

Все ваши функции хвостовые рекурсивные.

после самостоятельного вызова инструкции не осталось

означает: после самостоятельного вызова вы возвращаетесь из функции , т. Е. Больше не нужно выполнять код, и не то, что в функции больше нет строки кода.

Answer 3

Да;Я думаю, что ваш профессор имел в виду, что в любом случае, если окончательная инструкция является рекурсивной, то это хвостовая рекурсия.

Итак, все три примера хвостовой рекурсии.

Answer 4

Все три примера хвостовые рекурсивные.Вообще говоря, это хвостовая рекурсия, если результатом функции (выражение после ключевого слова return) является одиночный вызов самой функции. Никакой другой оператор не должен участвовать в самом внешнем уровне выражения .Если вызов сам по себе является только частью выражения, то машина должна выполнить вызов, но затем должна вернуться к оценке указанного выражения, то есть она была не в конце выполнения функции, а в серединевыражение.Это, однако, не относится ни к каким параметрам, которые может принимать рекурсивный вызов: там разрешено все, включая рекурсивные вызовы к себе (например, «return foo (foo (0));»).Оптимизация вызовов на переходы возможна только тогда для внешнего вызова.