Фридрих уже опубликовал простую версию функции size, которая будет работать для большинства деревьев. Однако решение не является «хвостово-рекурсивным», поэтому оно может вызвать переполнение стека для больших деревьев. В функциональных языках программирования, таких как F #, рекурсия часто является предпочтительным методом для таких вещей, как подсчет и другие агрегатные функции. Однако рекурсивные функции обычно используют кадр стека для каждого рекурсивного вызова. Это означает, что для больших структур стек вызовов может быть исчерпан до завершения функции. Чтобы избежать этой проблемы, компиляторы могут оптимизировать функции, которые считаются «хвостово-рекурсивными», так что они используют только один кадр стека независимо от того, сколько раз они рекурсируют. К сожалению, эта оптимизация не может быть просто реализована для любого рекурсивного алгоритма. Это требует, чтобы рекурсивный вызов был последним, что делает функция, тем самым гарантируя, что компилятору не придется беспокоиться о возврате в функцию после вызова, что позволяет ему перезаписывать кадр стека вместо добавления другого.
Чтобы изменить функцию size на хвостовую рекурсию, нам нужен какой-то способ, чтобы не вызывать ее дважды в случае непустого узла, чтобы этот вызов мог быть последним шагом функция, вместо сложения между двумя вызовами в решении Фридриха. Это может быть достигнуто с использованием нескольких различных методов, обычно с использованием аккумулятора или с использованием стиля продолжения продолжения. Более простое решение часто заключается в использовании аккумулятора для отслеживания общего размера, а не в качестве возвращаемого значения, в то время как стиль передачи продолжения является более общим решением, которое может обрабатывать более сложные рекурсивные алгоритмы.
Чтобы заставить шаблон аккумулятора работать для дерева, в котором мы должны суммировать как левое, так и правое поддеревья, нам нужен какой-то способ сделать один хвостовой вызов в конце функции, при этом убедившись, что оба поддеревья оцениваются. Простой способ сделать это - также накапливать правые поддеревья в дополнение к общему количеству, чтобы мы могли сделать последующие вызовы хвоста, чтобы оценить эти деревья, сначала оценивая левые поддеревья. Это решение может выглядеть примерно так:
let size t =
let rec size acc ts = function
| Empty ->
match ts with
| [] -> acc
| head :: tail -> head |> size acc tail
| Node (t1, _, t2) ->
t1 |> size (acc + 1) (t2 :: ts)
t |> size 0 []
Это добавляет параметр acc и параметр ts для представления общего количества и оставшихся неоцененных поддеревьев. Когда мы попадаем в заполненный узел, мы оцениваем левое поддерево, добавляя правое поддерево в наш список деревьев для последующей оценки. Когда мы достигаем пустого узла, мы начинаем оценивать любые накопленные нами ts, пока у нас не останется больше заполненных узлов или неоцененных поддеревьев. Это не самое лучшее решение для вычисления размера дерева, и в большинстве реальных решений для обеспечения его рекурсивного использования использовался бы стиль передачи продолжения, но это должно стать хорошим упражнением по мере знакомства с языком.