(How)
C^# You Are - 11 May 2008

It is Mother's Day so I have time for only a few questions related to academic how-tos.

1. How can you swap two integral values without using any additional space?  Answer

   This is an old assembly language trick.  Using the exlusive or (xor) operator (^ in C#) you can swap two integral values.  For each bit in the operands the xor operator sets the corresponding output bit to 1 if one, but not both, operands are 1.  This effectively allows for mirroring the inverse of the operands.  Here is a logic table.

   Op1	Op2	Result
   0	0	0
   0	1	1
   1	0	1
   1	1	0

   By combining a few calls to xor you can easily swap two integeral values, with restrictions.  The values must be of the same type and they must be integral values.  Any other values might or might not work.  Here is an example.

   public void Swap ( ref int op1, ref int op2 )
   {
      op1 ^= op2;    //op1 is a hybrid of both operands
      op2 ^= op1;    //op2 now equals the original op1 because op2 is being removed
      op1 ^= op2;    //op1 now equals the original op2 because op1 is being removed
   }

   
   
2. How can you calculate factorial without recursion?  Answer

   Most people learn recursion by solving factorial.  While this is a simple way to learn recursion the reality is that recursion is generally bad.  You should avoid it when possible because of the potential stack overflow that it can cause.  In most cases you can remove recursion by using an iterative algorithm (such as a for or while loop).  This avoids the stack overflow wihile still allowing for a recursive definition.

   public double Factorial ( int count )
   {
      double result = 1;
      while (count > 1)
      {
         result *= count;
         --count;
       };
   
      return result;
   }

   
   
3. Is it possible to create a tree traversal function that does not use recursion and still allows for arbitrarily deep trees?  Answer

   Yes it is.  By introducing a stack you can replicate just about any recursive function.  The biggest issue about such algorithms is that amount of memory they can eat up.  Here is an unoptimized algorithm for traversing a tree in LNR (left-node-right) order.  There are probably more optimal solutions available.  You could modify this algorithm to traverse the tree in other orders, if desired.

   static void InorderTraversal ( Tree tree, Action action )
   {
      Stack stack = new Stack();
   
      //Push the root
      stack.Push(tree);
     
      //Push each of the left nodes until we run out
      Tree current = tree.Left;
      while (current != null)
      {
         stack.Push(current);
         current = current.Left;
      };
   
      //Start popping nodes until we are done
      do
      {
         current = stack.Pop();
         if (current != null)
         {
            //Perform the action
            action(current);
   
            //Push the right child, if any and its leftmost children
            if (current.Right != null)
            {
               stack.Push(current.Right);
   
               //Push its leftmost children
               current = current.Right.Left;
               while (current != null)
               {
                  stack.Push(current);
                  current = current.Left;
               };
            };
         };
      } while (stack.Count > 0);
   }
   
   //For reference:
   class Tree
   {
      public Tree Left;
      public Tree Right;
      public int Id;
   }