Эта функция использует хвостовую рекурсию?

Question

Мне интересно, оптимизирует ли oCaml этот код для хвостовой рекурсии, и если да, то F#?

let rec sum xs =
  match xs with
    | [] -> 0
    | x :: xs' -> x + sum xs'

Answer 1

В рекурсивном случае (т. Е. В случае, когда xs не пусто), последней оцененной операцией является сложение. Чтобы функция была рекурсивной, последней оцененной операцией должен быть рекурсивный вызов sum.

Подобные функции обычно определяются с помощью вспомогательной функции с аккумулятором, чтобы сделать их хвостовой рекурсивной. В этом случае это будет функция, которая принимает список для суммирования и текущее значение суммы. Если список пуст, он вернет текущее значение суммы. Если список не пустой, он будет вызывать себя с хвостом списка и текущим значением суммы + заголовок списка в качестве аргументов. Функция суммы тогда просто вызовет вспомогательную функцию со списком и 0 в качестве текущего значения суммы.

Answer 2

Нет, этот код не является хвостовой рекурсией, и ocaml не будет преобразовывать его. Вы должны сделать это самостоятельно.

Я не знаю для F#, но я сомневаюсь, что это оптимизирует это.