C# How to make a recursive version of GetEnumerator()

Question

Can somebody give me advice on how to create a recursive version of GetEnumerator()? The well-known Towers of Hanoi problem may serve as an example that is comparable to the actual problem I have. A simple algorithm to show all moves for a stack of disks of height n is:

void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
{
  if (n > 0)
  {
    MoveTower0 (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower0 (n - 1, temp, finish, start);
  }
}

What I actually want to do is set up a class HanoiTowerMoves that implements IEnumerable and that enables me to iterate over all moves as follows:

foreach (Move m in HanoiTowerMoves) Console.WriteLine (m);

The first step towards a GetEnumerator() implementation seems to get rid of the MoveTower parameters. This can easily be done by using a stack. I also introduced a class Move that combines the parameters into a single variable.

class Move
{
  public int N { private set; get; }
  public Needle Start { private set; get; }
  public Needle Finish { private set; get; }
  public Needle Temp { private set; get; }

  public Move (int n, Needle start, Needle finish, Needle temp)
  {
    N = n;
    Start = start;
    Finish = finish;
    Temp = temp;
  }

  public override string ToString ()
  {
    return string.Format ("Moving disk from {0} to {1}", Start, Finish);
  }
}

Now MoveTower can be rewritten as follows:

void MoveTower1 ()
{
  Move m = varStack.Pop ();

  if (m.N > 0)
  {
    varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
    MoveTower1 ();
    Console.WriteLine (m);
    varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
    MoveTower1 ();
  }
}

This version must be called as follows:

varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
MoveTower1 ();

The next step towards an iterable version is to implement the class:

class HanoiTowerMoves : IEnumerable<Move>
{
  Stack<Move> varStack;
  int n; // number of disks

  public HanoiTowerMoves (int n)
  {
    this.n = n;
    varStack = new Stack<Move> ();
  }

  public IEnumerator<Move> GetEnumerator ()
  {
    // ????????????????????????????  }

  // required by the compiler:
  IEnumerator IEnumerable.GetEnumerator ()
  {
    return GetEnumerator ();
  }
}

Now the big question to me is: what does the body of GetEnumerator () look like? Can somebody solve this mystery for me?

Below is the code of Program.cs of the console application I created.

using System;
using System.Collections.Generic;
using System.Collections;

/* Towers of Hanoi
 * ===============
 * Suppose you have a tower of N disks on needle A, which are supposed to end up on needle B.
 * The big picture is to first move the entire stack of the top N-1 disks to the Temp needle,
 * then move the N-th disk to B, then move the Temp stack to B using A as the new Temp needle.
 * This is reflected in the way the recursion is set up.
 */

namespace ConsoleApplication1
{
  static class main
  {
    static void Main (string [] args)
    {
      int n;
      Console.WriteLine ("Towers of Hanoi");

      while (true)
      {
        Console.Write ("\r\nEnter number of disks: ");

        if (!int.TryParse (Console.ReadLine (), out n))
        {
          break;
        }

        HanoiTowerMoves moves = new HanoiTowerMoves (n);
        moves.Run (1); // algorithm version number, see below
      }
    }
  }

  class Move
  {
    public int N { private set; get; }
    public Needle Start { private set; get; }
    public Needle Finish { private set; get; }
    public Needle Temp { private set; get; }

    public Move (int n, Needle start, Needle finish, Needle temp)
    {
      N = n;
      Start = start;
      Finish = finish;
      Temp = temp;
    }

    public override string ToString ()
    {
      return string.Format ("Moving disk from {0} to {1}", Start, Finish);
    }
  }

  enum Needle { A, B, Temp }

  class HanoiTowerMoves : IEnumerable<Move>
  {
    Stack<Move> varStack;
    int n;            // number of disks

    public HanoiTowerMoves (int n)
    {
      this.n = n;
      varStack = new Stack<Move> ();
    }

    public void Run (int version)
    {
      switch (version)
      {
        case 0: // Original version
          MoveTower0 (n, Needle.A, Needle.B, Needle.Temp);
          break;

        case 1: // No parameters (i.e. argument values passed via stack)
          varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
          MoveTower1 ();
          break;

        case 2: // Enumeration
          foreach (Move m in this)
          {
            Console.WriteLine (m);
          }

          break;
      }
    }

    void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
    {
      if (n > 0)
      {
        MoveTower0 (n - 1, start, temp, finish);
        Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
        MoveTower0 (n - 1, temp, finish, start);
      }
    }

    void MoveTower1 ()
    {
      Move m = varStack.Pop ();

      if (m.N > 0)
      {
        varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
        MoveTower1 ();
        Console.WriteLine (m);
        varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
        MoveTower1 ();
      }
    }

    public IEnumerator<Move> GetEnumerator ()
    {
      yield break; // ????????????????????????????
    }

    /*
      void MoveTower1 ()
      {
        Move m = varStack.Pop ();

        if (m.N > 0)
        {
          varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
          MoveTower1 ();
          Console.WriteLine (m); ? yield return m;
          varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
          MoveTower1 ();
        }
      }
    */

    // required by the compiler:
    IEnumerator IEnumerable.GetEnumerator ()
    {
      return GetEnumerator ();
    }
  }
}

Childish

I don't understand the point of calling GetEnumerator recursively. Just write a recursive function, that call this method, its not hard. – Excelsior

Answer 1

Your approach is pretty good but I think you are overthinking the problem somewhat. Let's take a step back. You have a recursive algorithm:

void MoveTowerConsole (int n, Needle start, Needle finish, Needle temp) 
{   
  if (n > 0)   
  {
    MoveTowerConsole (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTowerConsole (n - 1, temp, finish, start);
  } 
} 

The algorithm's output is a bunch of console output. Suppose instead you wished the algorithm's output to be the sequence of strings that is going to be output to the console. Let's reason about what such a method would look like.

First off, we'll rename it. Second, its return type cannot be void. It must be IEnumerable<string>:

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    MoveTower(n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower(n - 1, temp, finish, start);
  } 
}

Is this right? No. We are not returning anything, we're still dumping to the console. What do we wish the iterator to yield? We wish the iterator to yield:

• all the moves necessary for the first recursive step
• the current move
• all the moves necessary for the second recursive step

So we modify the algorithm to yield those:

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(string move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return string.Format("Moving disk from {0} to {1}", start, finish);
    foreach(string move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

And we're done! Easy as that. There is no need to be defining a whole class to turn a recursive algorithm into a recursive enumerator; let the compiler do that work for you.

If you want to change this into a method that enumerates "moves", then do that:

IEnumerable<Move> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(Move move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return new Move(start, finish);
    foreach(Move move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

Now, I would criticize this code on the basis of efficiency. By making recursive enumerators in this manner, what you are doing is building a chain of n enumerators. When you need the next item, the top enumerator calls the next enumerator calls the next enumerator... down to the bottom, n deep. So each step now actually takes n steps to complete. I would be inclined to solve the problem without recursion for that reason.

Exercise: Rewrite the iterator block above so that it does no recursion at all. Your solution that uses an explicit stack is a step in the right direction, but it still does recursion. Can you adapt it so that no recursion is done?

If you are bent upon writing a class that implements IEnumerable<Move> then you can adapt the code above in a straightforward way:

class MoveIterator : IEnumerable<Move>
{
    public IEnumerator<Move> GetEnumerator()
    {
        foreach(Move move in MoveTower(whatever))
            yield return move;
    }

You can use yield return to implement a method that returns an enumerator or an enumerable.

Havard

1+ Faster than me with typing the solution. – Medical

Hello Eric, Thank you very much for the insightful and step by step way you present your solution. It was indeed a matter of looking at the problem in a wrong way that made me unable to see which way to go. Very instructive and informative! I actually already had a non-recursive solution that uses two stacks: see the answer below. Thanks again! John Pool Amersfoort Netherland – Childish

... Unfortunately, in my original problem, removing the recursion is not so straightforward. The recursive calls are buried in multi-level conditional statements, and turning the code into a state engine makes it pretty unreadable. So I think I will have to live with the nested enumerator solution -- which does not have to be a problem as long as performance is acceptable. – Childish

Answer 2

Your non-recursive solution is good -- building a pushdown automaton (a state machine with a stack, essentially) is a standard technique for building an iterative version of a recursive solution. And in fact, this is very similar to how we generate code for iterator and async blocks.

However in this specific case you don't need to pull out the heavy machinery of a pushdown automaton with a switch and a current state. You could just do this:

IEnumerable<Move> MoveTowerConsole (int size, Needle start, Needle finish, Needle temp) 
{   
  if (size <= 0) yield break;
  var stack = new Stack<Work>();
  stack.Push(new Work(size, start, finish, temp));
  while(stack.Count > 0)
  {
    var current = stack.Pop();
    if (current.Size == 1) 
      yield return new Move(current.Start, current.Finish);
    else
    {
       // Push the work in the *opposite* order that it needs to be done.
       stack.Push(new Work(current.Size - 1, current.Temp, current.Finish, current.Start));
       stack.Push(new Work(1, current.Start, current.Finish, current.Temp));
       stack.Push(new Work(current.Size - 1, current.Start, current.Temp, current.Finish));

     }
} 

You already know exactly what work you need to be doing after the current recursive step, so there's no need to bounce around a switch to put the three bits of work on the stack. Just queue all the work up at once for a given step.

Havard

Hello Eric, Thanks four your non-recursive solution! I must admit it looks a bit like magic to me. I have a vague notion of the big idea: when you pick a piece of ‘Work’ with a non-trivial size (i.e. > 1) from the queue, you break it up in three pieces – which individually are smaller than the original piece, otherwise the algorithm would not terminate – and you push those back in the queue ... – Childish

... Each time you encounter a trivial piece, you yield it, and you repeat this until there is nothing left in the queue. The Work class is just a container for all local variables that would go normally on the stack when recursion would be used. Is that the right way of looking at it? Is it possible to rewrite any recursive function this way? Do you have more examples, or a reference to an article on this subject? Thanks – John – Childish

@JohnPool: First off, my solution was wrong -- I should have been using a stack, not a queue. But yes, that's the basic idea. Not every recursive function can be rewritten as easily as this. – Havard

Answer 3

Non-recursive version:

// Non-recursive version -- state engine
//rta.Push (State.Exit);
//parameters.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
//MoveTower3 ();

enum State { Init, Call1, Call2, Rtrn, Exit }

{  
  ...

  #region Non-recursive version -- state engine
  static void MoveTower3 ()
  {
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          Console.WriteLine (m);
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          return;
      }
  }
  #endregion

  #region Enumeration
  static IEnumerable<Move> GetEnumerable (int n)
  {
    Stack<Move> moveStack = new Stack<Move> ();
    Stack<State> rta = new Stack<State> (); // 'return addresses'
    rta.Push (State.Exit);
    moveStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          yield return m;
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          yield break;
      }
  }
  #endregion
}

Childish