Un-recursive - part 1

I decided to write a cycle of posts about avoiding recursive calls in your algorythms. Recursion is the thing i hate to implement - it's hard to debug, it cost too much and so on. In this cycle i'm going to start with a common task - Tree Painting in depth - a task that could easyly solved with recursive calls - and show two ways to achieve the goal without recursive calls. After that i ll build parallels between this task and "common" recursive-solved task. Than i will implement quick sort and merge sort. Show/Hide

Tree Painting in Depth is a common task that could easyly be solved with recursive calls. Suppose we have a root node of a tree and a collection of children. Recursive method should paint root node and than calls itself for each child node. Pseudo-code for such method will look like Method(node root) { root.Paint(); for i = 1 to childern.Count { Method(children[i]); } } To avoid recursive calls in this algorythm we can use a stack of nodes to call Paint(). After painting a node we add its children at the beginning of the stack. Look at the implementation of this: We have a class Node

1:  class Node  
2:       {  
3:            public int Number { get; set; }  
4:            public Node[] Children { get; set; }  
5:            public void Paint()  
6:            {  
7:                 Console.WriteLine(Number + " was painted");  
8:            }  
9:       }  

Property Number at line 3 is just a name for node and Children is a collection of child nodes. Class Painter will paint a tree, accepting a root node building a stack of nodes which expect to be be called:

1:       class Painter  
2:       {  
3:            public void PaintWithStack(Node root)  
4:            {  
5:                 List<Node> stack = new List<Node>();  
6:                 stack.Add(root);  
7:                 while (stack.Count > 0)  
8:                 {  
9:                      var node = stack[0];  
10:                      node.Paint();  
11:                      stack.RemoveAt(0);  
12:                      if (node.Children != null)  
13:                      {  
14:                           for (int i = node.Children.Length - 1; i >= 0; i--)  
15:                           {  
16:                                stack.Insert(0, node.Children[i]);  
17:                           }  
18:                      }  
19:                 }  
20:            }  
21:       }  

A code to test algorytm is provided below. Lines 3-59 just instantiate a tree to paint. We call painter at line 61 to perform the task.

1:  static void Main(string[] args)  
2:            {  
3:                 var tree = new Node  
4:                 {  
5:                      Number = 1,  
6:                      Children = new[] {  
7:                           new Node  
8:                           {  
9:                                Number = 2,  
10:                                Children = new[] {  
11:                                     new Node  
12:                                     {  
13:                                          Number = 5,  
14:                                     },  
15:                                     new Node  
16:                                     {  
17:                                          Number = 6  
18:                                     }  
19:                                }  
20:                           },  
21:                           new Node  
22:                           {  
23:                                Number = 3,  
24:                                Children = new[] {  
25:                                     new Node  
26:                                     {  
27:                                          Number = 7  
28:                                     }  
29:                                }  
30:                           },  
31:                           new Node  
32:                           {  
33:                                Number = 4,  
34:                                Children = new [] {  
35:                                     new Node  
36:                                     {   
37:                                          Number = 8  
38:                                     },  
39:                                     new Node  
40:                                     {  
41:                                          Number = 9,  
42:                                          Children = new []{  
43:                                               new Node  
44:                                               {  
45:                                                    Number = 11  
46:                                               },  
47:                                               new Node  
48:                                               {  
49:                                                    Number = 12  
50:                                               }  
51:                                          }  
52:                                     },  
53:                                     new Node  
54:                                     {  
55:                                          Number = 10  
56:                                     }  
57:                                }  
58:                           }}  
59:                 };  
60:                 Painter p = new Painter();  
61:                 p.PaintWithStack(tree);  
62:                 Console.ReadKey();  
63:            }  

Output of this code will

 1 was painted  
 2 was painted  
 5 was painted  
 6 was painted  
 3 was painted  
 7 was painted  
 4 was painted  
 8 was painted  
 9 was painted  
 11 was painted  
 12 was painted  
 10 was painted  

which corresponds to the expected output.