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();
}

Solution 1

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.

Solution 2

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++.

Solution 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++.

Solution 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; }

View more solutions

Comments

[user1367292]

okay..I got my first doubt clear that You cant have recursive macros. What about the error in my sample code in the question...???

[sth]

You don't say what error you get, but the pr used recursively in the pr macro won't get expanded, and probably results in an "undefined function" error or some such.

[user1367292]

why pr(5-1) is treated as an undefined function call?? I've defined a macro so it should further expand to: ((5-1==1)? 1 : pr(5-1-1)) ....

[user1367292]

My intention is to know about recursive macros. I am not looking for a better way of printing some value.... I am not sure whether we can have a recursive macros or not.

[verdesmarald]

@user1367292 No, you can't have recursive macros. If it actually did keep replacing pr(x) with pr(x-1) it would just loop infinitely pr(x-1), pr(x-1-1), pr(x-1-1-1), etc...

[user1367292]

veredesmarald -- So, do you mean to say "We can't have recursive macros?". Also...is there any workaround available to achieve that?

[verdesmarald]

@user1367292 No. You cannot. What you are proposing does not make sense in the context of the pre-processor. How would you ever hit a base case for your recursion when all you are doing is replacing a string with itself + some other stuff over and over again?

[user1367292]

veredesmarald -- Thanks :-) Got it.

[Martin York]

Your argument is flawed. The macro replacement algorithm is repeated if your macros contains other macros (until no more substitution is done). So potentially it could do recursive macros. BUT the language spec explicitly forbids this by saying that once a macro is replaced it is removed from the potential list for subsequent replacement (within the same line).

[Zdeslav Vojkovic]

Thanks, fixed, didn't know about that rule.

[M.M]

Trying this in gcc 4.8.3 with -std=c99 gives error for the line OBSTRUCT(REPEAT_INDIRECT) (): error: 'REPEAT_INDIRECT' undeclared here (not in a function) . Moving the definition of REPEAT_INDIRECT up to before REPEAT does not fix.

[Paul Fultz II]

What is the output of the preprocesor?

[Austin Mullins]

The OBSTRUCT macro isn't expanded here because it isn't defined here. @Paul defines it in his original blog post.

[Admin]

This only answered the second qst, not the first.

[Avishay28]

@verdesmarald so the error will be "call to undefined function" or infinite loop?

[yangwenjin]

Elegant solution. This actually is lamda calculus.

[Alexander Torstling]

Great solution, but I can't get this to work on VS, seems like EAT doesn't work and always leaves the last iteration of REPEAT(0, macro) around.