Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursion in C# iterator

Tags:

iterator

c#

Is it possible to use recursion in an iterator implementing System.Collections.IEnumerable? I have a tree structure declared roughly like this:

public class Node
{
    public Node Sibling;
    public Node Child;
}

I would like to iterate over the nodes in a tree. I would like to do something like this (pseudocode, I guess this won't compile):

public class NodeIterator : System.Collections.IEnumerable
{
    Node m_root;

    public System.Collections.IEnumerator GetEnumerator()
    {
        recursiveYield(m_root);
    }

    System.Collections.IEnumeraton recursiveYield(Node node)
    {
        yield return node;
        if (node.Child)
        {
            recursiveYield(node.Child);
        }
        if (node.Sibling)
        {
            recursiveYield(node.Sibling);
        }
    }
}

Is this somehow possible? I realise this can be solved without recursion using a Node deque in the GetEnumerator function.

like image 995
Andreas Brinck Avatar asked Nov 17 '10 06:11

Andreas Brinck


People also ask

What is recursion in C and types?

Recursion is a routine that calls itself again and again directly or indirectly. There are two types of recursion in the C language Direct calling and Indirect calling. The calling refers to the recursive call. The recursion is possible in C language by using method and function.

What is the recursion with example?

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. For example, we can define the operation "find your way home" as: If you are at home, stop moving. Take one step toward home.

What is the use of recursion?

Recursion is a technique used to solve computer problems by creating a function that calls itself until your program achieves the desired result.


2 Answers

Yes, all you need is to iterate the return value from the call site. Like so:

IEnumerable<T> Recursive(Node node)
{
    yield return node;
    foreach (var siblingNode in Recursive(node.Sibling))
    {
        yield return siblingNode;
    }
    foreach (var childNode in Recursive(node.Child))
    {
        yield return childNode;
    }
}

For the record, this isn't better than using a queue to achieve e.g. breadth-first traversal. The memory requirement for something like this is identical in the worst case.

like image 75
John Leidegren Avatar answered Oct 22 '22 09:10

John Leidegren


No because the recursiveYield(Node node) function would return a collection and you can only yield an item

like image 22
ivo s Avatar answered Oct 22 '22 08:10

ivo s