va_arg... recursion: changing arguments and the using recursion

J

jononanon

Hello...

is there a nice and portable way of changing some variable arguments, and then passing these changed arguments to the same function as recursion??

Here's a non-general example:

#include <stdio.h>


int go(int num, ...)
{
int *p = &num;
int *p2 = p;
int i, n;
for (i = 1; i <= num; ++i)
printf("%d ", *(++p2));
putchar('\n');

for (p2 = p+num; p2 > p; --p2) {
n = *(p2);
if (n > 0) {
--(*p2);

//recurr
p2 = p+1;
go(num, *p2, *(p2+1), *(p2+2)); // lucky me... 4 total arguments
break;
}
}
}

int main(void)
{
go(3, 3, 3, 3);
return 0;
}



As is shown in the comment above, I'm just lucky with invoking 4 arguments in the recursion.
What could I do, if I don't know the number of arguments and want recursion?

Thanks.
 
J

jononanon

C99 draft standard comes to the rescue.

http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
On pdf-page 263 there is an example where the variable arguments are gathered in an array and then another function f2 is invoked with this array (and the number of array-elements).

So the way to hande it is: set up the array, and then call f2, and do the recursion on f2 (which has a fixed amount of arguments).
 
J

James Kuyper

Hello...

is there a nice and portable way of changing some variable arguments, and then passing these changed arguments to the same function as recursion??

Here's a non-general example:

#include <stdio.h>


int go(int num, ...)

You declared go() as returning a value of type 'int'; yet nowhere in
your code does it ever return a value. This is permitted if no call to
go() ever attempts to use the value which go() fails to return; but it's
a bad idea to rely upon that fact. If the function never returns a
value, its declaration should say so; if the declaration says it will
return a value, it should actually do so. I'm not sure which way of
fixing this is the one appropriate to your use.
{
int *p = &num;
int *p2 = p;
int i, n;
for (i = 1; i <= num; ++i)
printf("%d ", *(++p2));

This is undefined behavior. p points at only a single int. The standard
specifies that a pointer to a single int must be treated, for purposes
of pointer arithmetic, as if it were pointer to the only element of an
array of int with a length of 1. Therefore, p+i has defined behavior for
i == 0 or 1, but not for any other value of i. *(p+i) has defined
behavior only for i==0.
putchar('\n');

for (p2 = p+num; p2 > p; --p2) {

When num has any value other than 0 or 1, the expression p+num has
undefined behavior.
n = *(p2);

Since you only reach this line if p2>p, *p2 has undefined behavior, too.
If the code had defined behavior, the parentheses would be unnecessary.
if (n > 0) {
--(*p2);

//recurr
p2 = p+1;
go(num, *p2, *(p2+1), *(p2+2)); // lucky me... 4 total arguments

The last three arguments of go() all have undefined behavior.

My best guess is that you're assuming that *(&num+i), for i from 1 to
num, will retrieve the values of any additional int arguments of go().
I've used implementations of C where that would work; presumably it
works on the implementation you're using, or you wouldn't have even come
up with code so badly broken. However, it's not guaranteed to work, and
there are many real systems where it will fail catastrophically, which
is why that's NOT how you're supposed to access the additional arguments
of a variadic function.
break;
}
}
}

int main(void)
{
go(3, 3, 3, 3);
return 0;
}



As is shown in the comment above, I'm just lucky with invoking 4 arguments in the recursion.
What could I do, if I don't know the number of arguments and want recursion?

Given that all of your arguments are of type 'int', using a pointer to
the first element of an array of 'int', as you discussed in your other
message, is probably the best way to handle that. However, if the
arguments were not all of the same type, that wouldn't work.

Here's a re-write of your code that has defined behavior, and
demonstrates the correct way for a function with variable arguments to
extract them. To keep it reasonably close to your original code, I
change p from a pointer at a non-existent array into the name of an
actual array. Properly, it should validate that num<4; if num>3, the
recursive call to go() has undefined behavior. I wasn't sure what you'd
want to do in that case, so I left it up to you.

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

void go(int num, ...)
{
if(num <= 0)
return;

va_list ap;
int p[num + 1];
p[0] = num;

va_start(ap, num);
for(int i=1; i<num+1; i++)
{
p = va_arg(ap, int);
printf("%d ", p);
}
va_end(ap);

putchar('\n');

for(int *p2 = p + num; p2 > p; --p2)
{
if(*p2 > 0)
{
--(*p2);
go(num, p[1], p[2], p[3]);
break;
}
}
}

int main(void)
{
go(3, 3, 3, 3);
return 0;
}
 
J

jononanon

Thanks for those explanations and the code.

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

void go(int num, ...)
{
//...
int p[num + 1];

Does this work with Microsoft compiler? I seem to remember that the MS compiler complained that it is not a fixed length array (given variable num) and thus didn't work.
Is this a C90 or c99 feature?
Wow I just realized that we have C11!



I've just read about TAIL RECURSION, where a stack can be essentially reused, if the last call of a function is the recursive call. Well then tail recursion with reuse of the stack is not possible in portable C, right?

Quoting from wikip. on "Tail recursion":
"Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine."

So how on earth can one reuse the stack, for the recursive call (that is e.g. realized as a jump), if I don't even know where the heck the stack is??

That was your message wasn't it: don't make any assumption on the location of the stack variables

So does this mean that a portable C version of code, using tail recursion which reuses the stack... cannot be done in C???

Thanks.
 
J

John Reye

I said:
I've just read about TAIL RECURSION, where a stack can be essentially reused, if the last call of a function is the recursive call. Well then tail recursion with reuse of the stack is not possible in portable C, right?

Quoting from wikip. on "Tail recursion":
"Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine."

So how on earth can one reuse the stack, for the recursive call (that is e.g.  realized as a jump), if I don't even know where the heck the stack is??

That was your message wasn't it: don't make any assumption on the location of the stack variables

So does this mean that a portable C version of code, using tail recursionwhich reuses the stack... cannot be done in C???

Thanks.

Ah... of course one can do tail recursion!! ;) But one must get rid of
thinking of the typical function call, which always uses the stack
automatically.

Here's an example of tail-recursion which reuses the stack:


#include <stdio.h>

void go(int a1, int a2, int a3)
{
tail_recursion_label:
printf("%d %d %d\n", a1, a2, a3);
if (a3 > 0) {
--a3;
} else if (a2 > 0) {
--a2;
} else if (a1 > 0) {
--a1;
} else
return;
goto tail_recursion_label;
}

int main(void)
{
go(1, 2, 3);
return 0;
}
 
J

John Reye

For the poor souls who dislike goto... (it's not really needed here
anyway... I guess the word "jump" got me all exited!) Below are
changes for an endless while loop, with one point of exit: return
Here's an example of tail-recursion which reuses the stack:

#include <stdio.h>

void go(int a1, int a2, int a3)
{ while (1) {
  printf("%d %d %d\n", a1, a2, a3);
  if (a3 > 0) {
    --a3;
  } else if (a2 > 0) {
    --a2;
  } else if (a1 > 0) {
    --a1;
  } else
    return; }

}

int main(void)
{
  go(1, 2, 3);
  return 0;
}

The code somehow seems shows that tail-recursion is not really
powerful recursion, because the whole concept of setting up a new
stack is not necessary.
In particular: with tail-recursion, it is not possible to "spawn"
multiple instances of the function, by calling the function itself
more than once:

void go(int a1, int a2, int a3)
{
...
go(a1, a2, a3); go(a1, a2, a3); /* "spawn" 2 instances: not possible
via tail recursion. Here one needs to build up the stack for each
instance */
}
 
J

James Kuyper

Thanks for those explanations and the code.

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

void go(int num, ...)
{
//...
int p[num + 1];

Does this work with Microsoft compiler? I seem to remember that the MS compiler complained that it is not a fixed length array (given variable num) and thus didn't work.
Is this a C90 or c99 feature?
Wow I just realized that we have C11!

It's a C99 feature, and one supported by virtually every compiler that
makes any attempt at C99 conformance; I believe that this does not
include the M$ compiler.

For C90 code, if there were no upper limit on the value of num, you
would have to do something like this. However, the way your program is
written, the recursive call to go() always has exactly 3 arguments, but
will look for num arguments, so it has undefined behavior if num > 3. An
array with a fixed length of 4 will be adequate for any case where the
behavior is actually defined.

If you actually wanted to be able to handle a variable number of
arguments, the right approach is to define a non-recursive version of
your function which takes a variable number of arguments, and a
recursive subroutine which takes a va_list parameter. The va_list
parameter gives the subroutine access to the parameters of the variadic
function.
I've just read about TAIL RECURSION, where a stack can be essentially reused, if the last call of a function is the recursive call. Well then tail recursion with reuse of the stack is not possible in portable C, right?

When tail call optimization is possible, sufficiently good compilers can
often be counted on to perform it for you; you don't need to do anything.
Any routine which for which that optimization is possible can, instead,
be reorganized to perform a loop instead of being actually recursive,
which has the same effect. John Reyes has already provided an example,
so I won't bother. Notice that the non-recursive version is actually
simpler than the recursive version - this is not uncommon.
 
J

James Kuyper

On 04/26/2012 04:28 PM, James Kuyper wrote:
....
For C90 code, if there were no upper limit on the value of num, you
would have to do something like this. ...

"something like this" was, at one point during the editing of that
message, "dynamic memory allocation using malloc()". I'm not sure how
that phrase got lost. Sorry!
 
J

John Reye

James said:
"something like this" was, at one point during the editing of that
message, "dynamic memory allocation using malloc()". I'm not sure how
that phrase got lost. Sorry!

Ah ok, thanks.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,007
Latest member
obedient dusk

Latest Threads

Top