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

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 #, но я сомневаюсь, что это оптимизирует это.