title: Recursive Class Design Patterns: Options and Best Practices
body: <p>Dear all:  In advance, thank you for your time.</p>
  
  <p>Lately, I have decided to learn Objective-C (I am a long time C-hacker) and after reading the beautiful text by Kochan and diving into the Apple documentation I am still confused as to the best way to implement a recursive class (ie. a class in which an ivar has the type of
  the same class). For concreteness, let's assume we wish to implement a Binary Tree class.  First we have a basic node class, which I have simplified to:</p>
  
  <pre><code>@interface MMNode : NSObject {
      NSString *label;
  }
  </code></pre>
  
  <hr>
  
  <p>Now we can implement our tree in two different ways.  The first (and what I consider the more obvious approach) is placing the recursion in the class itself.</p>
  
  <pre><code>@interface MMTree : NSObject {
      MMNode *root;
      MMTree *leftTree;
      MMTree *rightTree;
  }
  @property (nonatomic, copy) MMNode *root;
  @property (nonatomic, retain) MMTree *leftTree;
  @property (nonatomic, retain) MMTree *rightTree;
  </code></pre>
  
  <hr>
  
  <p>The second method, which is used in the wonderful <a href="http://cocoaheads.byu.edu/code/CHDataStructures" rel="nofollow noreferrer">CHDataStructures.framework</a>, implements this data structure as follows:</p>
  
  <pre><code>typedef struct MMTreeNode {
      MMNode *node;
  //  union { 
  //      struct { 
              struct MMTreeNode *leftTree;
              struct MMTreeNode *rightTree;
  //      };
  //  };
  } MMTreeNode;
  
  
  @interface MMTreeStruct : NSObject {
      MMTreeNode *root;
  }
  </code></pre>
  
  <p>Here the solution is more "pointer-riffic", with the recursion pushed into
  the structure. (As mentioned in the comments, the anonymous structures and
  unions are not required.  However, since  many applications will require
  additional information at each node, I will leave the code as is).</p>
  
  <hr>
  
  <p>I have implemented both solutions and they work well.  The former seems more straightforward, more "OO"; the latter, more "C-centric" with slightly, more complicated source. </p>
  
  <p>Is the latter technique preferred?  If so, what is an objective reason? All I can determine is maybe the latter is more memory friendly as the structure has a fixed size. </p>
  
  <p>Again, thank you StackOverflow and thank you CocoaHeads.</p>
  
  <p><strong>UPDATE:</strong>  I should add, it seems that the CoreFoundation object <a href="http://developer.apple.com/documentation/CoreFoundation/Reference/CFTreeRef/" rel="nofollow noreferrer">CFTree</a>
  uses a similar structure implementation.</p>