Вложенные рекурсивные вызовы - это хвостовая рекурсия?

Question

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

Что мне менее понятно, как это определение применяется к вложенным вызовам. Я приведу пример:

func foo91(x int)
    if(x > 100):
        return x - 10
    else:
        return foo91(foo91(x+11))

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

Являются ли вложенные рекурсивные вызовы функций обычно значительными хвостовыми рекурсивными?

Answer 1

Ваше понимание только частично верно.

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

Теперь к вашему актуальному вопросу, внутренний вызов не является хвостовой рекурсией, потому что он должен вернуться к вашему вызову и сделать что-то остальное. Но внешний вызов хвостовой рекурсии.