1

我尝试做一个尾递归函数来计算列表的元素，遵循规则，使用累加器，但是当我像这样运行它时：

lstcountr [1..98765432];;

我明白了：

System.OutOfMemoryException：引发了“System.OutOfMemoryException”类型的异常。

这是我的功能（我认为是尾递归/高效）：

let lstcountr ls =
    let rec loop ls total = 
        match ls with
        | [] -> total
        | hd::tl -> loop tl total+1I
    loop ls 0I

这可以做得更好吗？

4

3 回答 3

8

你的函数不是尾递归的。

| hd::tl -> loop tl total+1I

应该

| hd::tl -> loop tl (total+1I)

运算符在函数调用之后被解释，通常在这种情况下你无法分辨，因为结果是相同的，但尾递归不是这样。

同样正如 Tejs 所说，您正在创建一个列表，其中包含太多导致您的OutOfMemoryException. 您是否尝试过使用seq { }?

于 2012-04-25T16:27:31.573 回答
5

太多的递归意味着你得到一个StackOverflowException，而不是OutOfMemoryException- 这是因为你试图一次创建一个 98765432 个元素的列表。

不管你的递归如何，这个作为参数传递的列表是在内存中创建的，而不是我可能会懒惰地添加。

于 2012-04-25T16:02:07.187 回答
2

以下是编写返回类型为多态的基于序列的版本的两种方法：

module Seq =
  open LanguagePrimitives

  let inline count items = Seq.fold (fun i _ -> i + GenericOne) GenericZero items

  //faster
  let inline count (items: seq<_>) =
    use e = items.GetEnumerator()
    let rec loop n =
      if e.MoveNext() then loop (n + GenericOne)
      else n
    loop GenericZero

这允许您使用最合适的类型计算长度：

let n : bigint = Seq.count {1I .. 987298234982374923847I}
let n : float = Seq.count {1I .. 987298234982374923847I}
于 2012-04-25T20:30:41.260 回答