这个函数是否使用尾递归？

Question

我想知道oCaml是否优化了这个代码是尾递归的,如果是这样的话F#？

let rec sum xs =
  match xs with
    | [] -> 0
    | x :: xs' -> x + sum xs'

Answer 1

在递归的情况下(即xs不为空的情况),最后一次评估的操作是加法.对于函数是尾递归,最后一次计算的操作需要是对sum的递归调用.

像这样的函数通常使用带有累加器的辅助函数来定义,以使它们是尾递归的.在这种情况下,这将是一个函数,它将列表求和,以及总和的当前值.如果列表为空,则返回总和的当前值.如果列表不为空,它将使用列表的尾部和sum的当前值+列表的头部作为参数调用自身.然后,sum函数将简单地使用list调用helper函数,并将0作为sum的当前值.

Answer 2

不,这段代码不是尾递归的,而ocaml也不会对它进行转换.你必须自己做.

我不知道F#,但我怀疑它会优化它.