## Concept: Recursive Yield on to a Common Channel.

Concept: Recursive Yield on to a Common Channel.

Public Class Node(Of T)
Public Property Left As Node(Of T)
Public Property Righ As Node(Of T)

Let's implement a simple iterator the return all of the values of all the nodes.

Public Iterator Function VisitNode(Of T)( N As Node(Of T)) As IEnumerable(Of T)
Yield N.Value
If n.Left IsNot Nothing Then
For Each visitedNode In VisitNode(N.Left)
Yield visitedNode
Next
End If
If n.Righ IsNot Nothing Then
For Each visitedNode In VisitNode(N.Righ)
Yield visitedNode
Next
End If
End Function

The Concept

Instead of repeatedly yielding values from a deeper level of recursion.
Why not pass some form of reference to the "Yielder" mechanism the ???
Now the iterator is O(n) rather then O(n2)

Public Iterator Function VisitNodes(Of T)(N As Node(Of T)) As IEnumerable(Of T)
Dim _Visit = Recursive Iterator(ByRef channel As ?? ,_N  As Node(Of T))
Yield On channel  _N.Value
' The value isnot yielded at the local scope of '
' the lambda _Visit '
' but on iterator: VisitNodes '
If N.Left IsNot Nothing _Visit(channel, N.Left)
If N.Righ IsNot Nothing _Visit(channel, N.Righ)
End Iterator
End Iterator

Restrictions

The iterator channel reference is locally scoped, akin to the functionality of the *cough* Goto {label name} *cough* and can not be pass out of the iterator method.

Open Challenge

Can any out there find away of achieving this without building a collection as you go and yielding them, or using the ForEach ... Yield method currently being used.

### 3 Comments On This Entry

Page 1 of 1

#### cfoley

22 August 2012 - 10:11 AM
To be clear, do you want to do a preorder traversal without using recursion? My first instinct is to use a stack. Something like:

let N = root node
let S = empty stack
while N != null
Yield N
S.push N
if N.hasLeftChild
N = N.leftChild
else if N.hasRightChild
N = N.rightChild
else if S.isEmpty
N = null
else
N = S.pop

The concept is fairly language agnostic and I think if you implement it in VB your scoping issues will vanish.
0

#### cfoley

22 August 2012 - 10:24 AM
Oops. That code I posted is clearly nonsense but the edit button won't work. I think this should do it:

let N = root node
let S = empty stack

while N != null
Yield N

if n.hasRightChild
S.push N

if N.hasLeftChild
N = N.leftChild
else if S.isEmpty
N = null
else
N = S.pop.rightChild
0

22 August 2012 - 12:23 PM
Look at the F# version.

// Yield the values of a binary tree in a sequence.
type Tree<'a> =
| Tree of 'a * Tree<'a> * Tree<'a>
| Leaf of 'a

// inorder : Tree<'a> -> seq<'a>
let rec inorder tree =
seq {
match tree with
| Tree(x, left, right) ->
yield! inorder left
yield x
yield! inorder right
| Leaf x -> yield x
}

It still doing a
For Each item In theIEnumerableReturnFromFunction
Yield item
Next

Each level of recursion, has yield the result(s) of the previous on. Eg
1
12
123
1234
12345

15 yields for 5 item sequence.
Inefficient.

I'm say why can't some object reference you can pass as argument parameter to a method. Which allows you to say .. by the way yield your values through this channel or pipe. So the compiler doesn't have to create new state machine for each level of recursion. Akin to the Tail Call Optimisation in the IL that saves creating a new stack frame, which allow deeper level of recursion (infinite).

When it could be
1 2 3 4 5

5 yields for a 5 item sequence.

The compiler could write a much more efficient state-machine for you.
0
Page 1 of 1