Почему первый хвост рекурсивен, а другой нет?
С учетом определения хвост-рекурсив ,
Вызов функции называется хвостовой рекурсией, если после возврата функции ничего не делать, кроме как возвращать ее значение.
В первой функции
fun fold1 f acc lst =
case lst of
[] => acc
| hd::tl => fold1 f (f (acc,hd)) tl
все остальные вычисления (f (acc, hd)) выполняются в качестве аргумента для fold1, что означает , после того как функция вернется, ничего не нужно делать, кроме как вернуть ее значение .
Inвторая функция,
fun fold2 f acc lst =
case lst of
[] => acc
| hd::tl => f (fold2 f acc tl, hd)
, все остальные вычисления (f (..., hd)) выполняются после выполнения fold2 f acc tl, что означает там означает что-то дляdo после того, как функция вернет , а именно compute f (..., hd).
Хвосто-рекурсивные функции имеют определяющую характеристику, заключающуюся в том, что самое внешнее выражение тела рекурсивной функции - это вызов самого себя.Если что-то еще вычисляется в функции, это должно произойти за до этого вызова, например, в качестве аргумента функции или в привязке let.
Например, следующий рефакторингfold1 также хвост-рекурсивен:
fun fold1 f acc0 [] = acc0
| fold1 f acc0 (x::xs) =
let val acc1 = f (acc0, x)
in fold1 f acc1 xs
end
и следующий рефакторинг fold2 не является:
fun fold2 f acc0 [] = acc0
| fold2 f acc0 (x::xs) =
let val acc1 = fold2 f acc0 xs
in f (acc1, x)
end
Поскольку после fold1 f acc1 xs больше ничего не нужно делатьконтекст вызова функции (стековый фрейм) можно безопасно отбросить.Более простой пример нерекурсивной и хвостовой рекурсии:
fun length [] = 0
| length (_::xs) = 1 + length xs
fun length xs =
let fun go [] count = count
| go (_::ys) count = go ys (1 + count)
in go xs 0
end