How to implement in ATS the following function based on tail-recursion?

Question

I have the following recursively defined function:

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]

How can I implement foo based on tail-recursion only.

Answer 1

You can do the followings, where the function loop is a tail-recursive function that keeps track of all necessary intermediate states. With tail-call optimization, this one will be optimized into a loop within a single frame, which is much faster than 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