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 ();
    }
  }
}

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.