indirect recursion

[David Mathog]

Lately I have been trying to modify a section of code (not mine) which
uses indirect recursion. By indirect recursion I mean:

func A -> func B -> func C -> func A etc.

Which got me wondering, what limits, if any, does C place on this sort
of call structure? Near as I can tell the standard is "anything goes",
allowing any number of different functions in the call stack, nested as
deep as whatever the physical limit of the machine is.

On a separate note, is it just me, or is indirect recursion
intrinsically horribly difficult to debug? In order to get anywhere on
this code static "depth" counters had to be added to all of the
functions. (It also didn't help that the functions were relatively
long, with some having multiple return points and others multiple lines
that called the next function.)

Thanks,

David Mathog

 

[Loïc Domaigné]

Hi David,

Lately I have been trying to modify a section of code (not mine) which
uses indirect recursion.  By indirect recursion I mean:

    func A -> func B -> func C -> func A etc.

Which got me wondering, what limits, if any, does C place on this sort
of call structure?  Near as I can tell the standard is "anything goes",
allowing any number of different functions in the call stack, nested as
deep as whatever the physical limit of the machine is.

my guess is that C doesn't impose any limit; but the OS does.

On a separate note, is it just me, or is indirect recursion
intrinsically horribly difficult to debug?  In order to get anywhere on
this code static "depth" counters had to be added to all of the
functions.  (It also didn't help that the functions were relatively
long, with some having multiple return points and others multiple lines
that called the next function.)

IMHO, "indirect recursion" is the hell to debug. You should only use
recursion, when it *simplifies* the code (understanding, less error
prone etc.). One application that comes to mind are parsers.

Cheers,
Loïc

 

[Eric Sosman]

Lately I have been trying to modify a section of code (not mine) which
uses indirect recursion. By indirect recursion I mean:

func A -> func B -> func C -> func A etc.

Which got me wondering, what limits, if any, does C place on this sort
of call structure? Near as I can tell the standard is "anything goes",
allowing any number of different functions in the call stack, nested as
deep as whatever the physical limit of the machine is.

On a separate note, is it just me, or is indirect recursion
intrinsically horribly difficult to debug? In order to get anywhere on
this code static "depth" counters had to be added to all of the
functions. (It also didn't help that the functions were relatively
long, with some having multiple return points and others multiple lines
that called the next function.)

See others' responses on the matter of limits.

To deal with multiple return sites, multiple call sites,
and so on, one useful technique is to use trivial wrappers.
Rename A -> Ax, B -> Bx, C -> Cx, leaving the bodies of the
functions untouched (still calling A, B, C). Then write the
A, B, C wrapper functions to do whatever logging and tracing
you like, maintaining depth counters, and so on, but forwarding
to Ax, Bx, Cx for the actual work:

char *A(int this, double that) {
char *result;
trace("-> A: this = %d, that = %g\n", this, that);
++depth;
result = Ax(this, that);
--depth;
trace("<- A: result = %s\n",
result ? result : "(null)");
return result;
}

This will approximately double the recursion depth, but if
the situation is tractable to begin with that's not likely to
be a big problem. If it *is* a problem, it'll probably just
provoke your failure mode a little sooner -- It's more likely
that you have a runaway recursion than that you have a finite
recursion that bottoms out just a little shy of system-imposed
limits.

 

[Guest]

| On a separate note, is it just me, or is indirect recursion
| intrinsically horribly difficult to debug? In order to get anywhere on
| this code static "depth" counters had to be added to all of the
| functions. (It also didn't help that the functions were relatively
| long, with some having multiple return points and others multiple lines
| that called the next function.)

Any recursion can be hard to debug. OTOH, I find OPC harder to debug,
where OPC is "other people's code".

At least if am developing all the code myself, I can understand of the
required recursion is really tail recursion, which is easy to implement
as a loop if you can get it all into the loop. It's when you have things
like A calling B twice, and B calling C twice, and C calling A twice, that
you really get into trouble.

One library I'm working on allows contructing a set of objects representing
display objects to be rendered. Many of the classes reference one or more
other obejcts, which are typically objects, but still can end up back at
the same class, maybe in the context of a different instance of that class,
or maybe the very same. The latter can be a big problem if not managed.
Typical cases will never have such a mess. But sometimes these could happen
so I still have to handle it in an appropriate way. A limit on the depth of
recursion is the simple way for now. And that's a depth counted in all
classes that reference objects.

 

[Kaz Kylheku]

Lately I have been trying to modify a section of code (not mine) which
uses indirect recursion. By indirect recursion I mean:

func A -> func B -> func C -> func A etc.

Which got me wondering, what limits, if any, does C place on this sort
of call structure? Near as I can tell the standard is "anything goes",
allowing any number of different functions in the call stack, nested as
deep as whatever the physical limit of the machine is.

On a separate note, is it just me, or is indirect recursion
intrinsically horribly difficult to debug?

Debug in what way?

Only if it's optimized tail recursion. Then you have no record of how
you reached any point in the computation and the states of the variables.
You're debugging a goto graph, albeit a more disciplined one.

In order to get anywhere on
this code static "depth" counters had to be added to all of the
functions.

Ah, you mean debug tracing. A good idea is to have a tracing system which
indents. I.e. you have just one depth counter. (Or one per execution context in
a multithreaded, multiprocessor or interrupt-driven system).

Been there, done that, on projects past.

The traces look like:

entering foo(arg == 42) {
entering bar() {
entering foo(arg == 43) {
...
}
}
}

The counter goes up when a traced function is entered, and decrements
when it is exited. Such indented traces are much easier to follow
than a flat trace.

(It also didn't help that the functions were relatively
long, with some having multiple return points and others multiple lines
that called the next function.)

With tracing systems like this you have to be disciplined about returning from
a function. All exit paths have to properly terminate the dynamic tracing
context for that function.

It's easier in C++ where you can do this with local objects that have
destructors.

If there are multiple places from which foo calls bar, then it's ambiguous.
You need to spit out some additional traces inside foo to make it clear.

Your tracing system can also maintain a stack of structures, which
allow a function to know what its parent is. I.e. when you enter the function,
the logic that sets up the tracing context can retrieve a pointer to the
top of this tracing stack, which tells it who the caller was. (And then it
will push a new record onto that stack representing /this/ function).
The caller can, at various points, record which line it is executing or
some other piece of information.

So then you can do things like ``enable tracing of function foo, but
only whenever it is called from bar, and only if some additional information
from the caller matches such and such a value.''.

 

[Richard Bos]

On a separate note, is it just me, or is indirect recursion
intrinsically horribly difficult to debug?

Not necessarily horribly, but for obvious reasons it is intrinsically
_more_ difficult to debug than normal recursion.

(It also didn't help that the functions were relatively long, with some
having multiple return points and others multiple lines that called the
next function.)

Blah. Code like that is a sign that either the original programmer was
incompetent, or that it should have been written as a state machine in
the first place.

Richard

 

[David Mathog]

Been there, done that, on projects past.

The traces look like:

entering foo(arg == 42) {
entering bar() {
entering foo(arg == 43) {
...
}
}
}

The counter goes up when a traced function is entered, and decrements
when it is exited. Such indented traces are much easier to follow
than a flat trace.

Excellent idea. I had similar messages but without indents and yours is
much easier to read.

Thanks

 

[Gene]

Lately I have been trying to modify a section of code (not mine) which
usesindirectrecursion.  ByindirectrecursionI mean:

    func A -> func B -> func C -> func A etc.

Which got me wondering, what limits, if any, does C place on this sort
of call structure?  Near as I can tell the standard is "anything goes",
allowing any number of different functions in the call stack, nested as
deep as whatever the physical limit of the machine is.

Any call places an activation record on the stack. Successive calls
with no return cause the stack to grow. When you're out of stack, the
program crashes. Whether simple or complex recursion or just deep
static nesting, the reason and result are the same.

On a separate note, is it just me, or isindirectrecursion
intrinsically horribly difficult to debug?  

Well-designed code is easier to debug than crufty code. Complex
recursion can add another layer of confusion to an already bad
situation. But it can also provide a wonderfully elegant way of doing
complex things. A chief example is recursive descent parsing. Here
I've set up a very tiny example of the indented nesting tracing idea
suggested by others, which is absolutely the way to go. And I've
applied it in a tiny parser to show how it's used:

The trace system:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

char *stack[10000];
int sp = 0;

void trace(char *fmt, ...)
{
va_list ap;
printf("\n%*s", sp, "");
va_start(ap, fmt);
vprintf(fmt, ap);
va_end(ap);
}

void begin(char *name)
{
trace("%s {", name);
stack[sp++] = strdup(name);
}

void end(void)
{
char *name = stack[--sp];
trace("} %s", name);
free(name);
}

A really tiny recursive descent parser for expressions like (a + b) *
3.

void die(char *msg)
{
fprintf(stderr, "\ndie: %s\n", msg);
exit(1);
}

int ch; // lookahead character

int peek(void)
{
trace("peek = %c", ch);
return ch;
}

void advance(void)
{
do ch = getchar(); while (ch == ' ');
trace("lookahead = %c", (ch == '\n') ? '$' : ch);
}

void term(void);
void factor(void);

void expr(void)
{
begin("expr");
term();
while (peek() == '+') {
advance();
term();
}
end();
}

void term(void)
{
begin("term");
factor();
while (peek() == '*') {
advance();
factor();
}
end();
}

void factor(void)
{
begin("factor");
if (isalnum(peek())) {
advance();
}
else if (peek() == '(') {
advance();
expr();
if (peek() != ')') die("expected )");
advance();
}
else
die("expected factor");
end();
}

int main(void)
{
advance();
expr();
return 0;
}


C:\>tracexample
(a + b) * 3

lookahead = (
expr {
term {
factor {
peek = (
peek = (
lookahead = a
expr {
term {
factor {
peek = a
lookahead = +
} factor
peek = +
} term
peek = +
lookahead = b
term {
factor {
peek = b
lookahead = )
} factor
peek = )
} term
peek = )
} expr
peek = )
lookahead = *
} factor
peek = *
lookahead = 3
factor {
peek = 3
lookahead = $
} factor
peek = $
} term
peek = $
} expr
C:\>