4 Replies - 2745 Views - Last Post: 08 July 2013 - 12:27 PM

#1 rgfirefly24  Icon User is online

  • D.I.C Lover
  • member icon


Reputation: 294
  • View blog
  • Posts: 1,533
  • Joined: 07-April 08

Head Recursion vs Tail Recursion

Posted 08 July 2013 - 09:44 AM

So i'm not a big math person, nor have I really studied anything about algorithms, so as to which is better in my situation I am not entirely sure.

So to set the stage we are using VB.NET as a backend and JQuery to do our javascript work. We have a page where someone can setup the Organizational structure of their business and save it for later use and reporting. Since we are allowing them to dynamically add/subtract from the hierarchy structure we are needing to use recursion to put the new nodes where they belong in the tree. Basically we have the parent node which can have between 0 and N children. Those children can themselves have between 0 and N children. Currently we are adding things to the tree using the Tail up aproach staring right to left.

'newNode is the node to be inserted
'currentNode is the node being looked at
'parentDesc is the identified as to where the newNode should be placed as a child
'index number of child nodes
'ChildNodes is a list of COSNode setup to be defaulted to empty list

Private Sub TraverseNodeTree(ByVal newNode As COSNode, ByRef currentNode As COSNode, ByVal parentDesc As String, ByVal index As Integer)
            ' Turtles ... all the way down ...
            While index > -1
                TraverseNodeTree(newNode, currentNode.ChildNodes(index), parentDesc, currentNode.ChildNodes(index).ChildNodes.Count - 1)
                index -= 1
            End While

            If currentNode.CosDescription = parentDesc Then
                currentNode.ChildNodes.Add(newNode)
            End If
        End Sub



we use the same idea in Javascript aswell to add the new nodes on the fly. Now, I guess the actual question. Would attempting a Head recursion be more efficient in this case or maybe switching to a left to right instead of right to left flow?

This post has been edited by rgfirefly24: 08 July 2013 - 09:47 AM


Is This A Good Question/Topic? 1
  • +

Replies To: Head Recursion vs Tail Recursion

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 8001
  • View blog
  • Posts: 13,710
  • Joined: 19-March 11

Re: Head Recursion vs Tail Recursion

Posted 08 July 2013 - 09:55 AM

"Tail recursion" is an optimization to recursive calls which eliminates the need for a new stack frame if there is no more work to be done before the return from the recursive call, allowing the programmer to write a formally recursive call without the performance penalties and possibility of bottoming out the stack. Strictly speaking, this is "tail call optimization" since it applies to any function call, but "tail recursion" is the commonly used term.

Tail call optimization is generally a language feature: a particular language definition might require it, or a particular implementation might offer it. I don't know if VB.NET offers TCO, but I'm pretty sure that Javascript does not at the present time. (though I believe there are proposals to introduce this in revision 6 of the ECMA spec)


I've never heard of "head recursion". What is it?
Was This Post Helpful? 1
  • +
  • -

#3 rgfirefly24  Icon User is online

  • D.I.C Lover
  • member icon


Reputation: 294
  • View blog
  • Posts: 1,533
  • Joined: 07-April 08

Re: Head Recursion vs Tail Recursion

Posted 08 July 2013 - 11:02 AM

I might be using the wrong terminology (Infact i'd wager I am). From my understanding of it, I would start at head and check it against parentDesc and if it matches add else traverse down to the first child node and check that one. If that matches add it their, if not then go to it's first child. If no matches happen down the left then move up and go down the next available path, ect.

This post has been edited by rgfirefly24: 08 July 2013 - 11:03 AM

Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 8001
  • View blog
  • Posts: 13,710
  • Joined: 19-March 11

Re: Head Recursion vs Tail Recursion

Posted 08 July 2013 - 11:08 AM

That sounds like a pre-order traversal to me. This would be done recursively, yes, and for a reasonably sized tree shouldn't cause major performance hitches.

You can traverse a tree in pre-order, post-order, or in-order, and the process is the same. The only difference is when you work on the present node relative to visiting the left and the right nodes.
Was This Post Helpful? 1
  • +
  • -

#5 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Head Recursion vs Tail Recursion

Posted 08 July 2013 - 12:27 PM

Also can be done non-recursively. See Tutorial
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1