Introduction - Basics

First step, the basics. I want to explain how macro expansion works and a couple of rules that we need to keep in mind (Rules 1 and 2 are for beginners while Rules 3 and 4 are worth reviewing). So lets start with a basics and looking at how they work:

#define SIMPLE_DEFINITION REPLACEMENT
#define MACRO(params) STUFF_TO_REPLACE_MACRO_WITH

The first define is a simple replacement. Whenever the compiler comes across SIMPLE_DEFINTION it will replace it with whatever REPLACEMENT does.
The second define is an actual macro. When the compiler comes across MACRO(params) it will replace whatever with whatever we want to replace it with. Macros are evaluated in left to right

RULE 1: Whenever we come across a macro the compiler replaces the macro with whatever the macro text says to replace with. These macros are replaced in left to right order

Rule 2: Macros parameters are directly substituted into the macro (and are evaluated [This is important for the next part]) so watch out for when brackets are needed.

Now lets consider a simple macro definitions and look at how it expands:

#define MULTIPLY(x, y) x * y
MULTIPLY(x, y) // This evaluates to x * y

MULTIPLY(x, MULTIPLY(y, z)) // This evaluates to x * y * z
// The evaluation goes as follows
(1) Expand the first MULTIPLY -> x * MULTIPLY(y, z)
(2) Expand the second MULTIPLY -> x * y * z 

MULTIPLY(x + y, z) // This expands to x + y * z not (x + y) * z
MULTIPLY((x + y), z) // This expands to (x + y) * z

Rule 3: During each macro expansion, the parameters are replaced and evaluated

The next one looks how macros are expanded when there is a chain of macros and this is where stuff gets interesting:

#define EMPTY() // This MACRO doesn't do anything
#define EVAL(...) __VA_ARGS__ // This is a simple identity macro
#define HELLO() "Hello World"

HELLO() // Expands to "Hello World" as expected

Now lets complicate stuff and consider what happens in the following example:

HELLO EMPTY() () //  This evaluates to HELLO () not "Hello World"

/*
 Lets go over its evaluation 

 We go left to right and the first macro we can expand is EMPTY()
 Note, its not HELLO because we don't actually call it as HELLO ()
 and so the compiler just sees it as a normal define not a macro right now.
 As a result expanding EMPTY() we end up with
*/
HELLO () // Now note this doesnt expand further
/*
 This is because the processor has evaluated all tokens at this point.
 How do we get past this problem?
*/

Now, lets look at how to actually evaluate the macro so we end up with "Hello World"

// As the function hints, lets use EVAL and see how it changes our result
EVAL ( HELLO EMPTY() () ) // This evaluates to "Hello World"
/*
  The preprocessor first evaluates the EVAL macro.
  Now the one thing we need to remember is Rule 2.
  The processor puts in the evaluated version of the parameter.
  As a result we evaluate the EVAL macro and will output the
  evaluated version of HELLO EMPTY() ().
  As a result we get the following code
*/
// First pass
HELLO () // Now this will get evaluated as its the result of the EVAL macro
// Send and final pass
"Hello World"

On a side, here's a summary of the rules. Try to see why they would expand the way they do as a result of Rule 3. This is probably one of the most important rules.

HELLO() // "Hello World"
HELLO EMPTY() () // HELLO ()
HELLO EMPTY EMPTY() () () // HELLO EMPTY() ()

EVAL(HELLO EMPTY () ()) // "Hello World"
EVAL(HELLO EMPTY EMPTY() () ()) // HELLO ()
EVAL(EVAL(HELLO EMPTY EMPTY() () ())) // "Hello World"

Rule 4: When a macro is expanded, if the macro name appears during its expansion it is not allowed to be expanded further. HOWEVER, this is only if the macro shows up during its expansion. (This is easier to show then explain)

#define RECURSE(x) x RECURSE(x)
RECURSE(x) // This will evaluate to x RECURSE(x)

EVAL(RECURSE(x)) // This will also still evaluate to x RECURSE(x)
/*
  Lets look at a bit more in depth of what happened
  EVAL(RECURSE(x)) evaluates to x RECURSE(x)
  This is because EVAL causes the RECURSE(x) to evalulate
  As a RECURSE(x) expands to x RECURSE(x), the second RECURSE(x)
  call is not allowed to be called and stays as RECURSE(x)!
*/

This means no direct mutual recursion allowed either

#define MUTA() a MUTB()
#define MUTB() b MUTA()

MUTA() // This expands to a b MUTA()
/* Lets have a look
(1)   MUTA() expands giving us a MUTB()
(2)   Now we evaluate the expansion and find MUTB().
      This expands and gives us a b MUTA(). Now note
      this expression is a result of evaluating the MUTA()
      expansion. As a result this new MUTA() is not evaluated
(3)   evaluating a b MUTA() simply gives us the same
*/