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

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

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

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;
}

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

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}
Источник

4 ответа

Решение

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

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

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

Следовательно, неофициально, функция является хвостовой рекурсивной, когда возможна оптимизация хвостового вызова, и когда целью хвостового вызова является сама функция. Эффект более или менее такой же, как если бы функция содержала цикл, и вместо вызова самого себя, вызов 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);
}

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

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

Источник

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

Итак, все три примера являются хвост-рекурсивными.

Источник

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

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

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

Источник

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

Источник
Другие вопросы по тегам