Having difficulties with recursive tree traversal in functional programming; how do I avoid a StackOverflow?

Question

I am struggling with the Scala course on Coursera, and I realised that I am having serious problems dealing with recursion, particularly tree traversal in a functional manner. To generalize the problem (for the sake of a wider relevance) I have sets that are defined as binary trees, individual nodes are either Empty or Non-empty which both extend the custom binary tree abstract class. If a node is an instance of Non-empty it has; a left child, a right child, and an element of class MyObj.

Given the function findMax I implemented in 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)
}

• why does my code cause a StackOverflow?

• am I missing something fundamental with regards to functional programming? I have had pretty serious problems with union of such sets as well (see my previous question), which is supposedly near-trivial and a much better implementation of the union is a "simple one liner".

  I have been hearing that you have to change the way you think in order to succeed in functional programming. Then, when you get how things work, one supposedly reaches the Nirvana, world peace will be achieved and world will be a beautiful place to live on...

  However, so far it's been pure frustration... What's worse is that the other students don't seem to be struggling all that much, the forums are riddled with optimisation discussions, while I am stuck not having a clear idea of what's going on. I take that to mean one of the following three alternatives:

  a) I am just too dumb to understand the stuff

  b) the other students have some prior understanding of functional programming

  c) I am doing something wrong

Any help on getting a grip of things is warmly welcome. PS: Please try to not give away anything regarding the solution, all I want is to understand why my code doesn't work as intended, and how I should be thinking.

Answer 1

Your function stack overflows because you always call it with the same argument (which are left and right, i.e. this.left and this.right). when calling treeAcc recursively, you should call it with the subtrees of the current node, not with the subtrees of the root.

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))  
}