Before this, I would recommend reading the Macro Basics Tutorial.  In the article we discussed rule 4 that disallowed recursion explicitly. However, this doesn't mean we cant do recursion. The rule states that if we come across the current macros name it is flagged as a macro that cannot be evaluated. The trick here is that we need an indirect macro that refers to macro we want to recurse. If the indirect macro doesn't evaluate during the macros expansion, we can then evaluate it to recurse. This is hard to follow so lets start start building it up with example. The correct code is at the end (so feel free to skip the derivation) but I want to show where everything comes from.

So first step, lets create an indirection to the recursion macro and see what happens:

#define RECURSE(x) x RECURSE_INDIRECT EMPTY () () (x)
// This the same as #define RECURSE(x) x DEFER(RECURSE_INDIRECT) () (x)
// I just kept the EMPTY() in to make it a bit more explicit

#define RECURSE_INDIRECT() RECURSE
RECURSE(x) // This evaluates to x RECURSE(x)
/*
  This example is similar to the mutual recursion example
  When the RECURSE macro is expanded, RECURSE_INDIRECT () is also
  This causes RECURSE to be added as a result of the initial RECURSE
  and as a result we disallow it from expanding more
*/

So the problem is we need to delay the evaluation of the indirection macro so that it is expanded only AFTER the initial macro. How do we do this? We make use of the delay macro discussed before. By adding an EMPTY() we can delay the execution by one step. Lets look at the updated macro

#define EXPR(...) __VA_ARGS__
#define RECURSE(x) x RECURSE_INDIRECT EMPTY () () (x)
#define RECURSE_INDIRECT() RECURSE

RECURSE(x) // This expands to x RECURSE_INDIRECT () (x)!
/*
  When we call RECURSE(x) after parameter replacement
  [x RECURSE_INDIRECT EMPTY () (x)] is evaluated to
  [x RECURSE_INDIRECT(x)]. By adding the EMPTY() we were able to
  defer the execution of RECURSION_INDIRECT.
*/

EXPR(RECURSE(x)) // This expands to x x RECURSE_INDIRECT () (x)
/*
  We did it!
  This is the same as expanding EXPR(x RECURSE_INDIRECT () (x))
  Since we expand RECURSION_INDIRECT macro (because it is a paramter to
  the EXPR macro), the RECURSE that is added as a result of the expansion
  can actually be expanded. This is because RECURSE was a result of
  the RECURSION_INDIRECT not the RECURSE macro!

  As a result when we evaluate the result of the
  expansion RECURSE is evaluated and we have no recursed!.
*/

EXPR(EXPR(RECURSE(x))) // This expands to x x x RECURSE_INDIRECT () (x)

Note, we must make sure the indirection macro doesn't actually call the macro its indirecting explicitly. At which point the indirection would be added as a result of the expansion of the indirection!

#define RECURSE(x) x RECURSE_INDIRECT EMPTY () (x)
#define RECURSE_INDIRECT(x) RECURSE(x)

RECURSE(x) // x RECURSE_INDIRECT (x)

EXPR(RECURSE(x)) // x x RECURSE_INDIRECT (x)
/* Rewrite it as EXPR(x RECURSE_INDIRECT (x)) and we can see we
   RECURSE_INDIRECT as a result of expanding RECURSE_INDIRECT
*/

EXPR(EXPR(RECURSE(x))) // As expected we get x x RECURSE_INDIRECT (x)

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
*/