Это функционирует хвостовая рекурсия использования?
Я задаюсь вопросом, оптимизирует ли oCaml этот код, чтобы быть рекурсивным хвостом и раз так делает F#?
let rec sum xs =
match xs with
| [] -> 0
| x :: xs' -> x + sum xs'
2 ответа
В рекурсивном случае (т. Е. В случае, когда xs не пусто) последней оцененной операцией является сложение. Чтобы функция была хвостовой рекурсивной, последней оцененной операцией должен быть рекурсивный вызов sum.
Подобные функции обычно определяются с помощью вспомогательной функции с аккумулятором, чтобы сделать их хвостовой рекурсией. В данном случае это будет функция, которая принимает список для суммирования и текущее значение суммы. Если список пуст, он вернет текущее значение суммы. Если список не пуст, он будет вызывать себя с хвостом списка и текущим значением суммы + заголовком списка в качестве аргументов. Затем функция суммы просто вызовет вспомогательную функцию со списком и 0 в качестве текущего значения суммы.
Нет, этот код не является хвостовым рекурсивным, и ocaml не будет его преобразовывать. Вы должны сделать это сами.
Я не знаю, что такое F #, но сомневаюсь, что он поможет это оптимизировать.