尾递归组合
我有这样的代码：
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
它看起来是递归的尾部，但是我一直在使用堆栈溢出。 任何想法如何使其工作？
combinations是尾递归的。 你的问题在于@操作符。 用它附加一个列表迭代整个列表，所以当你的acc变大时，你会得到一个SO。
你可以在这里看到， @运算符不是尾递归。 非优化版本看起来像这样： let rec (@) xy = match x with [] -> y | (h::t) -> h :: (t @ y) let rec (@) xy = match x with [] -> y | (h::t) -> h :: (t @ y) 。
为了解决这个问题，有几个选择：
如果你不关心顺序，你可以编写一个tail-recursive方法来预先得到这样的结果：
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]