3

我在 Coursera 上的 Scala 课程上苦苦挣扎，我意识到我在处理递归方面遇到了严重的问题，特别是以功能方式遍历树。为了概括这个问题（为了更广泛的相关性），我有定义为二叉树的集合，单个节点是Empty或Non-empty两者都扩展自定义二叉树抽象类。如果一个节点是Non-empty它的一个实例；一个左孩子、一个右孩子和一个 class 的元素MyObj。

鉴于findMax我实现的功能Non-empty：

def findMax: MyObj = {

  // traverse left, traverse right, check with the candidate 
  def treeAcc(tree:MyBTSet, cand: MyObj, f: (MyObj,MyObj) => MyObj): MyObj = {
    if (tree.isEmpty) cand
    else f(treeAcc(left,cand,f), treeAcc(right,cand,f))  
  }

  treeAcc(this,elem, (t1,t2) => if (t1.text > t2.text) t1 else t2)
}

  • 为什么我的代码会导致 StackOverflow？

  • 我是否缺少有关函数式编程的基本知识？我在联合这些集合方面也遇到了非常严重的问题（请参阅我之前的问题），这被认为是微不足道的，并且联合的更好实施是“简单的单线”。

    我一直听说你必须改变你的思维方式才能在函数式编程中取得成功。然后，当你了解事情的运作方式时，据说一个人达到了涅槃，世界将实现和平，世界将成为一个美丽的居住地......

    然而，到目前为止，这纯粹是沮丧......更糟糕的是其他学生似乎并没有那么挣扎，论坛上充斥着优化讨论，而我却不知道发生了什么. 我认为这意味着以下三种选择之一：

    a）我太笨了，无法理解这些东西

    b) 其他学生对函数式编程有一定的了解

    c) 我做错了什么

热烈欢迎任何有关掌握事物的帮助。PS：请尽量不要泄露有关解决方案的任何内容，我只想了解为什么我的代码无法按预期工作，以及我应该如何思考。

4

1 回答 1

1

您的函数堆栈溢出，因为您总是使用相同的参数（即leftand right，即this.leftand this.right）调用它。当递归调用treeAcc时，你应该用当前节点的子树调用它，而不是根的子树。

def treeAcc(tree:MyBTSet, cand: MyObj, f: (MyObj,MyObj) => MyObj): MyObj = {
  if (tree.isEmpty) cand
  else f(treeAcc(tree.left,cand,f), treeAcc(tree.right,cand,f))  
}
于 2013-04-26T10:20:19.787 回答