Can we have recursive macros?

Question

I want to know if we can have recursive macros in C/C++? If yes, please provide a sample example.

Second thing: why am I not able to execute the below code? What is the mistake I am doing? Is it because of recursive macros?

# define pr(n) ((n==1)? 1 : pr(n-1))
void main ()
{
    int a=5;
    cout<<"result: "<< pr(5) <<endl;
    getch();
}

Answer 1

Macros don't directly expand recursively, but there are workarounds. When the preprocessor scans and expands pr(5):

pr(5)
^

it creates a disabling context, so that when it sees pr again:

((5==1)? 1 : pr(5-1))
             ^

it becomes painted blue, and can no longer expand, no matter what we try. But we can prevent our macro from becoming painted blue by using deferred expressions and some indirection:

# define EMPTY(...)
# define DEFER(...) __VA_ARGS__ EMPTY()
# define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)()
# define EXPAND(...) __VA_ARGS__

# define pr_id() pr
# define pr(n) ((n==1)? 1 : DEFER(pr_id)()(n-1))

So now it will expand like this:

pr(5) // Expands to ((5==1)? 1 : pr_id ()(5 -1))

Which is perfect, because pr was never painted blue. We just need to apply another scan to make it expand further:

EXPAND(pr(5)) // Expands to ((5==1)? 1 : ((5 -1==1)? 1 : pr_id ()(5 -1 -1)))

We can apply two scans to make it expand further:

EXPAND(EXPAND(pr(5))) // Expands to ((5==1)? 1 : ((5 -1==1)? 1 : ((5 -1 -1==1)? 1 : pr_id ()(5 -1 -1 -1))))

However, since there is no termination condition, we can never apply enough scans. I'm not sure what you want to accomplish, but if you are curious on how to create recursive macros, here is an example of how to create a recursive repeat macro.

First a macro to apply a lot of scans:

#define EVAL(...)  EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__

Next, a concat macro which is useful for pattern matching:

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__

Increment and decrement counters:

#define INC(x) PRIMITIVE_CAT(INC_, x)
#define INC_0 1
#define INC_1 2
#define INC_2 3
#define INC_3 4
#define INC_4 5
#define INC_5 6
#define INC_6 7
#define INC_7 8
#define INC_8 9
#define INC_9 9

#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8

Some macros useful for conditionals:

#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~, 1,

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0

#define BOOL(x) COMPL(NOT(x))

#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t

#define IF(c) IIF(BOOL(c))

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

Putting it all together we can create a repeat macro:

#define REPEAT(count, macro, ...) \
    WHEN(count) \
    ( \
        OBSTRUCT(REPEAT_INDIRECT) () \
        ( \
            DEC(count), macro, __VA_ARGS__ \
        ) \
        OBSTRUCT(macro) \
        ( \
            DEC(count), __VA_ARGS__ \
        ) \
    )
#define REPEAT_INDIRECT() REPEAT

//An example of using this macro
#define M(i, _) i
EVAL(REPEAT(8, M, ~)) // 0 1 2 3 4 5 6 7

So, yes with some workarounds you can have recursive macros in C/C++.

Answer 2

Your compiler probably provides an option to only pre-process, not actually compile. This is useful if you are trying to find a problem in a macro. For example using g++ -E:

> g++ -E recursiveMacro.c

# 1 "recursiveMacro.c"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "recursiveMacro.c"

void main ()
{
    int a=5;
    cout<<"result: "<< ((5==1)? 1 : pr(5 -1)) <<endl;
    getch();
}

As you can see, it is not recursive. pr(x) is only replaced once during pre-processing. The important thing to remember is that all the pre-processor does is blindly replace one text string with another, it doesn't actually evaluate expressions like (x == 1).

The reason your code will not compile is that pr(5 -1) was not replaced by the pre-processor, so it ends up in the source as a call to an undefined function.

Answer 3

You're not supposed to have recursive macros in C or C++.

The relevant language from the C++ standard, section 16.3.4 paragraph 2:

If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file’s preprocessing tokens), it is not replaced. Furthermore, if any nested replacements encounter the name of the macro being replaced, it is not replaced. These nonreplaced macro name preprocessing tokens are no longer available for further replacement even if they are later (re)examined in contexts in which that macro name preprocessing token would otherwise have been replaced.

There's some wiggle room in this language. With multiple macros that invoke one another, there's a grey area where that wording doesn't quite say what should be done. There is an active issue against the C++ standard regarding this language lawyer problem; see http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#268 .

Ignoring that language lawyer issue, every compiler vendor understands the intent:

Recursive macros are not allowed in C or in C++.

Answer 4

Most likely you are not able to execute it because you can't compile it. Also if it would compile correctly, it would always return 1. Did you mean (n==1)? 1 : n * pr(n-1).

Macros can't be recursive. According to chapter 16.3.4.2 (thanks Loki Astari), if the current macro is found in the replacement list, it is left as is, thus your pr in the definition will not be changed:

If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file's pre- processing tokens), it is not replaced. Further, if any nested replacements encounter the name of the macro being replaced, it is not replaced. These nonreplaced macro name preprocessing tokens are no longer available for further replacement even if they are later (re)examined in contexts in which that macro name preprocessing token would otherwise have been replaced.

Your call:

cout<<"result: "<< pr(5) <<endl;

was converted by preprocessor into:

cout<<"result: "<< (5==1)? 1 : pr(5-1) <<endl;

During this, the definition of pr macro is 'lost', and compiler shows an error like "‘pr’ was not declared in this scope (fact)" because there is no function named pr.

Use of macros is not encouraged in C++. Why don't you just write a function?

In this case you could even write a template function so it will be resolved in compile time, and will behave as a constant value:

template <int n>
int pr() {  pr<n-1>(); }

template <>
int pr<1>() { return 1; }

Answer 5

TLDR. True recursion itself is easy done by duplicating macros in two names, with each referencing other. But usefulness of this feature is doubtful, because this requires nested conditional macro to make recursion finite. All conditional macro-operators are essentially multiline, because #else and #endif lines must be separate lines (serious cpp limitation), which means, that conditional macro-definitions are impossible by design (thus, recusion itself would be useless).

Answer 6

You can't have recursive macros in C or C++.