尾部递归组合

Question

我有这样的代码:

    let rec combinations acc listC = 
        match listC with
        | [] -> acc 
        | h::t ->
            let next = [h]::List.map (fun t ->  h::t) acc @ acc
            combinations next t 

它看起来是尾部递归的，但是我一直得到堆栈溢出。有什么好主意吗?

Answer 1

combinations为尾部递归。你的问题是@操作符。用它附加一个列表来迭代整个列表，所以当你的acc变大时，你会得到一个so。

您可以在这里看到，@操作符不是尾部递归的。未优化的版本如下:let rec (@) x y = match x with [] -> y | (h::t) -> h :: (t @ y) .

要解决这个问题，有两个选项:

1. 如果你不关心顺序，你可以写一个尾部递归方法，像这样把结果放在前面:

   let rec prepend lst1 lst2 = match lst1 with | [] -> lst2 | head::tail -> prepend tail (head::lst2)

> prepend [1;2;3;4] [5;6;7;8];; 
val it : int list = [4; 3; 2; 1; 5; 6; 7; 8]

如果您关心顺序，您可以编写一个方法来首先反转列表，然后添加它。当然，这样做的缺点是，它需要两倍的内存，因为您要分配一个额外的列表来保存原始列表的反向版本。您可以重用前面的函数来编写如下内容:

let prepend2 lst1 lst2 = prepend (prepend lst1 []) lst2

> prepend2 [1;2;3;4] [5;6;7;8];; 
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]