Как реализовать в ATS следующую функцию на основе хвостовой рекурсии?

Question

У меня есть следующая рекурсивно определенная функция:

fun foo(n: int): int =
  ifcase
    | n = 0 => 0
    | n = 1 => 1
    | n = 2 => 1
    | (* else *) => foo(n-1) + foo(n-3)
  // end of [ifcase]

Как я могу реализовать foo основано только на хвостовой рекурсии.

Answer 1

Вы можете сделать следующее, где функция loop является хвостовой рекурсивной функцией, которая отслеживает все необходимые промежуточные состояния. С оптимизацией хвостового вызова, этот будет оптимизирован в цикл внутри одного кадра, который намного быстрее, чем foo,

implement bar (n) = let
  fun loop (k:int, n1:int, n2:int, n3:int): int =
    if k = n
    then n1 + n3
    else loop (k+1, n2, n3, n1+n3)
in
  ifcase
    | n = 0 => 0
    | n = 1 => 1
    | n = 2 => 1
    | _ => loop(3, 0, 1, 2)
end