indirect recursion
David Mathog
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
Richard Heathfield
> 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?
There are certainly no explicit upper limits, and there are no
explicit lower limits that I'm aware of.
> 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.
Or the logical limit, imposed by the operating system or host
environment. This could be lower than the physical limit of the
machine (because the system may be trying to facilitate multiple
simultaneously executing processes), or it could be higher (because
the system could swap out if need be).
> On a separate note, is it just me, or is indirect recursion
> intrinsically horribly difficult to debug?
Not intrinsically, no, but it is easy to get into a ghastly mess if
you don't design the code carefully.
> 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.)
Er, yes, I can see how that wouldn't help.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
This line unintentionally left unblank
Loïc Domaigné
> 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
--
My Blog: http://www.domaigne.com/blog
"The trouble with programmers is that you can never tell what a
programmer is doing until it’s too late." -- Seymour Cray.
Gordon Burditt
>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?
Not much, except that all bets are off if you run out of automatic
storage.
>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.)
I think it depends on what you are trying to debug. If the problem
is a tendancy to infinitely recurse, that's often messy even in the
simple recursion A calls A.
On occasion I have ended up simplifying a function into two, thereby
turning direct recursion into indirect recursion, and I thought the
result was much easier to understand. That usually involved
consolidating calls from several places into one, though. It won't
work that way in general.
Eric Sosman
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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
phil-new...@ipal.net
| 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.
--
-----------------------------------------------------------------------------
| Phil Howard KA9WGN | http://linuxhomepage.com/ http://ham.org/ |
| (first name) at ipal.net | http://phil.ipal.org/ http://ka9wgn.ham.org/ |
-----------------------------------------------------------------------------
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.''.
Daniel Molina Wegener
Hash: SHA512
Loïc Domaigné <loic.d...@googlemail.com>
on Friday 14 August 2009 12:24
wrote in comp.lang.c:
> 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.
True, the stack size precisely...
>
>> 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.
Not too much, if you can follow the code in your mind first, and
then set the proper breakpoints, is not a hard task. Personally, usually
I do the initial implementation with recursion, but then I do later
implementation replacing the recursion with the proper algorithm.
The common example is the tree traversal problems...
>
> Cheers,
> Loïc
> --
> My Blog: http://www.domaigne.com/blog
>
> "The trouble with programmers is that you can never tell what a
> programmer is doing until it?s too late." -- Seymour Cray.
Best regards,
- --
.O. | Daniel Molina Wegener | FreeBSD & Linux
..O | dmw [at] coder [dot] cl | Open Standards
OOO | http://coder.cl/ | FOSS Developer
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (FreeBSD)
iQIcBAEBCgAGBQJKiGN2AAoJEHxqfq6Y4O5NuJ8QAKptah5m7+e+Txx409C0vUHT
HL1XG5PrxGlAM30CcBntkd7/ZpBrS3rVE1uSyT5DtzRMhsr86z3ygk5ULM0Hj97h
T/Ykn/sY5QcgnZp0f1IuH+ABBV//lwZluJEizwVfVYMusiG4juyutkvUsOTQg3H9
q98GTww0zhZQH9j8aS4sghDT+tlOaIyourDihEszW1/bTf+8I5r21KAgzK4t7U6y
vjApu4/9sUvgl0CO8bJlkNSQ2k1kW3+dP4HgfbCKIgtVY3NXiLnDo2Ge4/n0RenG
Xd8gqGJdUSn5Y5v8CszwTLgsC9/ul34zf4aNcnAhr+cy/52JHnad+N2F4tTUtIUS
om/CX7ld7iO2aP4iBnu2d/wWCr1a6abYYn+sfuI381VBVj3M93hG451+9QSveZKD
5zx7ccy0RwC1RdjIYcM32ebGdgKk8fFpb0OplXr4cszc6Us5FG5S/wzju1Lyl8pA
yDNFcxGBTThgt4amHKcp5Wb5F56RnFwrYtx4avh9aWVZmyb0TpsaGLFscxtzQZJi
WqI4YwWZGcKV0G/ipzLb4gwxkul409AeR0QNZG1Di4Si/I1q3WpLVRr968kwT3M0
aq5GpaEvFY5IUsdgN/RO5nK8TgSCOj5C98ICev4HILNh0d6NlvJSmOoNH/kzOoD+
gz3gZ/cgwkBTY8u7RX+R
=9lhG
-----END PGP SIGNATURE-----
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
>
> 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:\>