На этом шаге мы наметим план дальнейшего изложения.
Хвостовая линейная рекурсия, или "концевая" рекурсия, - это разновидность линейной рекурсии, когда рекурсивные условия вызывают метод только один раз. Но в отличие от обычной линейной рекурсии хвостовой рекурсивный вызов - это последнее выполняемое методом действие. Например, функция (1.15) относится к хвостовой рекурсии, так как в рекурсивном условии она ничего не делает с результатом вызова функции. Это значит, что она вернёт значение, полученное непосредственно в начальном условии. Кроме того, такие функции могут требовать большего количества параметров для сохранения промежуточных результатов, которые будут использоваться в начальных условиях для получения конечного результата. Хвостовые рекурсивные методы встречались ранее в примерах 2.3, 2.5 и 2.6.
В предыдущих шагах все методы, за исключением методов из 63 шага, уменьшали размер задачи на 1 или 2. Однако в последующих шагах представлены в основном алгоритмы, которые делят размер задачи пополам. В этом случае рекурсивные вызовы решают одну задачу в половину размера исходной, так как методы вызывают себя лишь однажды. Некоторые авторы относят эту стратегию к методу "разделяй и властвуй". Однако мы будем использовать этот термин только для тех алгоритмов, которые должны будут решить несколько независимых подзадач, размеры которых - лишь часть исходной задачи. Такие алгоритмы мы рассмотрим позже. Наконец, особенность хвостовой рекурсии в том, что она тесно связана с итерацией, и в дальгейших шагах мы рассмотрим эту связь.
Со следующего шага мы приступим к рассмотрению логических функций.
