尾递归组合 [英] Tail Recursive Combinations

问题描述

我有此代码:

    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 

它看起来是尾递归的，但是我一直在堆栈中溢出.关于如何使它起作用的任何想法?

It looks tail recursive, but I keep getting stack overflows with it. Any ideas on how to make it work?

推荐答案

combinations是尾递归的.您的问题出在@运算符上.在列表后面加上一个迭代将对整个列表进行迭代，因此当您的acc变大时，您将得到一个SO.

combinations is tail recursive. Your problem is with the @ operator. Appending a list with it iterates the whole list, so as your acc becomes large, you will get a SO.

您可以在此处看到表示@运算符不是尾递归.未优化的版本如下:let rec (@) x y = match x with [] -> y | (h::t) -> h :: (t @ y).

You can see here, that the @ operator is not tail recursive. The non-optimized version looks like: let rec (@) x y = match x with [] -> y | (h::t) -> h :: (t @ y).

要解决此问题，有两种选择:

To get around this problem, there are a couple of options:

1. 如果您不关心顺序，则可以编写尾部递归方法来像这样添加结果:

1. If you don't care about order, you could write a tail-recursive method to prepend the result like this:

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

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]

1. 如果您关心顺序，则可以编写一种方法来首先反转列表，然后在列表前添加.当然，这样做的缺点是，由于要分配一个额外的列表来保存原始列表的反向版本，因此它将需要两倍的内存.您可以重用以前的函数来编写类似以下内容的文件:

1. If you care about order, you could write a method to first reverse the list and then prepend it. The drawback of this, of course, is that it will require twice as much memory since you are allocating an additional list to hold the reversed version of the original list. You can reuse the previous function to write something like this:

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

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]

这篇关于尾递归组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！