如何在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