title: Scala tree recursive fold method
body: <p>Given the following definition for a (not binary) tree:</p>
  
  <pre><code>sealed trait Tree[+A]
  case class Node[A](value: A, children: List[Node[A]]) extends Tree[A]
  object Tree {...}
  </code></pre>
  
  <p>I have written the following <strong>fold</strong> method:</p>
  
  <pre><code>def fold[A, B](t: Node[A])(f: A ⇒ B)(g: (B, List[B]) ⇒ B): B =
    g(f(t.value), t.children map (fold(_)(f)(g)))
  </code></pre>
  
  <p>that can be nicely used for (among other things) this <strong>map</strong> method:</p>
  
  <pre><code>def map[A, B](t: Node[A])(f: A ⇒ B): Node[B] =
    fold(t)(x ⇒ Node(f(x), List()))((x, y) ⇒ Node(x.value, y))
  </code></pre>
  
  <p>Question: can someone help me on how to write a tail recursive version of the above <strong>fold</strong>?</p>