1: namespace Recursion5
2: { 3: /// <summary>
4: /// Question:
5: /// For a given positive int n prints all binary numbers of length n
6: /// </summary>
7: class Program
8: { 9: static void Main(string[] args)
10: { 11: for (int i = 1; i < 5; i++)
12: { 13: Console.WriteLine("Recursive binaries for {0}", i); 14: RecursivePrintBinaries(i);
15:
16: Console.WriteLine("Iterative binaries for {0}", i); 17: InterativePrintBinaries(i);
18: }
19: Console.ReadLine();
20: }
21:
22: /// <summary>
23: /// Interative print binaries method
24: /// </summary>
25: /// <param name="n"></param>
26: public static void InterativePrintBinaries(int n)
27: { 28: System.Collections.BitArray array = new System.Collections.BitArray(n,false);
29:
30: //calculate the total runs - each bit can be 1 or 0 and there are n of those
31: int totalRuns = (int)Math.Pow(2,n);
32: do
33: { 34: //First of all print the current array
35: PrintBinary(array);
36:
37: //flip the first bit (and potentialy cause a chain reaction that will flip other bits as well
38: FlipBit(array);
39:
40: totalRuns--;
41: }
42: while (totalRuns > 0);
43: }
44:
45: private static void FlipBit(System.Collections.BitArray array)
46: { 47: //flip the last bit
48: array[array.Length - 1] = !array[array.Length - 1];
49:
50: for (int j = array.Length- 1; j > 0; j--)
51: { 52: //if previous bit is fliped to zero - the current bit should flip to one
53: if (!array[j])
54: { 55: array[j - 1] = !array[j - 1];
56: }
57: else
58: { 59: //stop the bit flipping loop
60: break;
61: }
62: }
63: }
64:
65: /// <summary>
66: /// Utility method that prints the bits array
67: /// </summary>
68: /// <param name="array"></param>
69: private static void PrintBinary(System.Collections.BitArray array)
70: { 71: for (int i = 0; i < array.Length; i++)
72: { 73: Console.Write(array[i] ? 1 : 0);
74: }
75: Console.WriteLine();
76: }
77:
78: /// <summary>
79: /// Print Binaries method
80: /// </summary>
81: /// <param name="i"></param>
82: public static void RecursivePrintBinaries(int i)
83: { 84: RecursivePrintBinaries(new bool[i], 0);
85: }
86:
87: /// <summary>
88: /// Recursive method that processes array of bits at index idx
89: /// </summary>
90: /// <param name="array"></param>
91: /// <param name="idx"></param>
92: private static void RecursivePrintBinaries(bool[] array, int idx)
93: { 94: //end of processing - print the outcome
95: if (idx >= array.Length)
96: { 97: PrintBinary(array);
98: return;
99: }
100:
101: //The first options is to use 0 at index idx in the bit array
102: array[idx] = false;
103: RecursivePrintBinaries(array, idx + 1);
104:
105: //The first options is to use 1 at index idx in the bit array
106: array[idx] = true;
107: RecursivePrintBinaries(array, idx + 1);
108: }
109:
110: /// <summary>
111: /// Utility method that prints the bool array
112: /// </summary>
113: /// <param name="array"></param>
114: private static void PrintBinary(bool[] array)
115: { 116: for (int i = 0; i < array.Length; i++)
117: { 118: Console.Write(array[i]?1:0);
119: }
120: Console.WriteLine();
121: }
122: }
123: }