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

Question

Can someone give me advice on how to create a recursive version of GetEnumerator ()? The famous Towers of Hanoi problem can be an example comparable to the actual problem that I have. A simple algorithm for displaying all moves for a stack of disks with 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); } } 

Actually, I want to create a HanoiTowerMoves class that implements IEnumerable and allows me to iterate over all the moves as follows:

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

The first step to implementing GetEnumerator () seems to be getting rid of the MoveTower parameters. This can be easily done using the stack. I also introduced the Move class, which combines parameters into one 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 (mN > 0) { varStack.Push (new Move (mN - 1, m.Start, m.Temp, m.Finish)); MoveTower1 (); Console.WriteLine (m); varStack.Push (new Move (mN - 1, m.Temp, m.Finish, m.Start)); MoveTower1 (); } } 

This version should be called as follows:

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

The next step to the 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 for me the big question is: what does the body of GetEnumerator () look like? Can anyone solve this mystery for me?

The following is the Program.cs code 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 (ie 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 (mN > 0) { varStack.Push (new Move (mN - 1, m.Start, m.Temp, m.Finish)); MoveTower1 (); Console.WriteLine (m); varStack.Push (new Move (mN - 1, m.Temp, m.Finish, m.Start)); MoveTower1 (); } } public IEnumerator<Move> GetEnumerator () { yield break; // ???????????????????????????? } /* void MoveTower1 () { Move m = varStack.Pop (); if (mN > 0) { varStack.Push (new Move (mN - 1, m.Start, m.Temp, m.Finish)); MoveTower1 (); Console.WriteLine (m); ? yield return m; varStack.Push (new Move (mN - 1, m.Temp, m.Finish, m.Start)); MoveTower1 (); } } */ // required by the compiler: IEnumerator IEnumerable.GetEnumerator () { return GetEnumerator (); } } } 

Answer 1

Your approach is very good, but I think you think too much about the problem. Let me 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 output of the algorithm is a bunch of console output. Suppose instead that you want the output of the algorithm to be a sequence of lines that will be output to the console. Explain how this method will look.

First, we will rename it. Secondly, its return type cannot be invalid. It should be an 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 it correct? No. We are not returning anything, we are still dumping it to the console. What do we need for the iterator to yield? We want the iterator to give:

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

So, we modify the algorithm to obtain the following values:

 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 you're done! Easy. There is no need to define an integral class to turn a recursive algorithm into a recursive enumerator; let the compiler do it for you.

If you want to change this to a method that lists "moves", do the following:

 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 based on efficiency. Thus, making recursive counters, you create a chain of n counters. When you need the next element, the top enumerator calls the next enumerator, which calls the next enumerator ... down, n deep. Thus, each step now actually performs n steps. For this reason, I would be inclined to solve the problem without recursion.

Exercise . Rewrite the iterator block above so that it doesn't return at all. Your solution using an explicit stack is a step in the right direction, but it still does the recursion. Can you adapt it so that there is no recursion?

If you tend to write a class that implements IEnumerable<Move> , you can easily and easily adapt the code above:

 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 enumerated one .

Answer 2

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

However, in this particular case, you do not need to pull out a heavy launcher machine with a switch and current status. 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 needs to be done after the current recursive step, so there is no need to abandon the switch to put three bits of work on the stack. Just get all the work done right away for a given step.

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 = (mn <= 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 (mn-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 (mn-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 = (mn <= 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 (mn-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 (mn-1, m.temp, m.finish, m.start)); s = State.Init; break; case State.Rtrn: s = rta.Pop (); break; case State.Exit: yield break; } } #endregion }