Почему это не хвост рекурсивный?

Question

Я работаю над книгой Функциональное программирование в реальном мире , и я попытался найти собственный пример рекурсии хвоста, прежде чем читать пример книги (листинг 10.2, с. 265). Пример книги работает; шахта вызывает переполнение стека.

Я обнаружил, что если я использую аргумент кортежа или предварительно вычисляю a + accum, тогда мой будет работать. Я хочу понять почему.

let rnd = new System.Random()
let test2 = List.init 1000000 (fun _ -> rnd.Next(-50, 51))

let rec sum2 list accum =
  match list with
  | [] -> accum
  | a::b -> sum2 b a + accum

let result = sum2 test2 0

printfn "%d" result

Answer 1

sum2 b a + accum

Обратите внимание, что это анализируется как (sum2 b a) + accum, а не sum2 b (a + accum).

Так что это вызывает sum2 b a.Затем он берет результат этого вызова и добавляет к нему accum.Таким образом, последнее вычисленное выражение - это сложение, а не вызов sum2.Таким образом, вызов sum2 не является хвостовым вызовом.

Answer 2

Может быть, компилятор читает

a::b -> (sum2 b a) + accum

вместо

a::b -> sum2 b (a + accum)