标签: tailrecursion-modulo-cons

我对Scala很新,所以请原谅我的无知!我正在尝试迭代以最大值为界的整数对.例如,如果最大值为5,则迭代应返回:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

我选择尝试并以递归方式将其作为Stream返回:

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

没有tailrec注释,代码可以工作:

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), …

我正在通过"现在学习Prolog"在线书籍来获取乐趣.

我正在尝试编写一个谓词,该谓词遍历列表的每个成员并使用累加器向其中添加一个谓词.我已经很容易做到了,没有尾递归.

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

但我已经读过,出于性能原因,最好避免这种类型的递归.这是真的？总是使用尾递归被认为是"好习惯"吗？是否值得努力使用累加器来养成良好的习惯？

我试图将此示例更改为使用累加器,但它会反转列表.我怎么能避免这个？

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).

我正在研究Okasaki的Purely Functional Data Structures并尝试构建F#实现的东西.我也正在阅读本书中列出的练习(有些非常具有挑战性).好吧,我坚持练习3.4,它要求修改WeightBiasedLeftistHeap的合并功能,使其在单个传递中执行,而不是原始的2传递实现.

我还没弄清楚如何做到这一点,并希望得到一些建议.在SO上有另一篇文章,其中一个人通过几乎内联makeT函数在SML中完成它.我开始走这条路线(在评论部分3.4首先尝试.但是放弃了这种方法,因为我认为这真的不是在一次传递中执行(它仍然是'直到达到叶子然后展开并重建树).我在解释那仍然是两次合并时错了吗？

这是我完整实施WeightBiasedLeftistHeap的链接.

以下是我在F#中尝试这样做的失败:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB …

如在此代码中:

import Data.Char
groupsOf _ [] = []
groupsOf n xs = 
    take n xs : groupsOf n ( tail xs )

problem_8 x = maximum . map product . groupsOf 5 $ x
main = do t <- readFile "p8.log" 
      let digits = map digitToInt $concat $ lines t
      print $ problem_8 digits

我意识到在Haskell中许多程序构造并且似乎存储了一些中间结果,例如groupsOf上面代码中的列表.以上代码是来自Haskell网站的 Euler项目问题​​8的参考答案.原始问题要求在一个非常长的数字链中连续5位数的最大乘积,例如45343231635723421312443535767983456.因此代码将计算所有产品并将其存储为列表.在其他语言中,我认为它们只会保留一个临时的最大值,并丢弃任何较小的值.

那么groupsOf真的存储了所有中间结果吗？如果问题扩大怎么办？它会分配太多内存吗？

我看到了几个append向列表实现元素的例子,但都没有使用尾递归.如何在功能风格中实现这样的功能？

 (define (append-list lst elem) expr)

我搜索过高和低,似乎找不到很多与运行时复杂性,递归和java相关的资料.

我目前正在学习Algorithms类中的运行时复杂性和Big-O表示法,而且我在分析递归算法时遇到了麻烦.

private String toStringRec(DNode d)
{
   if (d == trailer)
      return "";
   else
      return d.getElement() + toStringRec(d.getNext());
}

这是一个递归方法,它将简单地迭代一个双向链表并打印出元素.

我唯一能想到的是它的运行时复杂度为O(n),因为递归方法调用的数量将取决于DList中的节点数量,但我仍然觉得不舒服这个答案.

我不确定我是否应该考虑添加d和d.getNext().

还是我只是完全偏离轨道和运行时间复杂度为常数,因为它做的事就从检索的元素DNodes在DList？

例如，这不是尾调用：

map _ [] = []
map f (x : xs) = f x : map f xs

由(:)数据构造函数保护的递归调用，因此它不会像其他语言中的等价物那样构建巨大的堆栈。它是这样工作的：

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : 3 : map (+1) (3 : [])
2 : 3 : 4 : map (+1) []
2 : 3 : 4 : []

为什么不

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : …

这是一个将两个列表附加在一起的算法:

Domains
list= integer*

Predicates
nondeterm append(list, list, list)

Clauses
append([], List, List) :- !.
append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

Goal
append([9,2,3,4], [-10,-5,6,7,8], Ot).

结果是一个列表[9,2,3,4,-10,-5,6,7,8],它保存在" Ot"中.

我的问题是,这是如何工作的？

我理解的是,在每个递归调用中,在第一个列表中,只得到尾部作为列表(从而减小它的大小1直到它为止[]),第二个参数" List2"根本不变,第三个参数.起初它是[],并且在每次递归调用之后你得到它的尾巴,但是因为它是[],它保持不变[].

那么,为什么突然间,在第三个参数(" Ot")中我们有附加的列表？有人可以一步一步地解释这个算法吗？