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

Discussion in 'C Programming' started by jononanon@googlemail.com, Apr 25, 2012.

  1. Guest

    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.
     
    , Apr 25, 2012
    #1
    1. Advertising

  2. Guest

    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).
     
    , Apr 25, 2012
    #2
    1. Advertising

  3. James Kuyper Guest

    On 04/25/2012 02:02 PM, wrote:
    > 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;
    }
     
    James Kuyper, Apr 26, 2012
    #3
  4. Guest

    Thanks for those explanations and the code.

    On Thursday, April 26, 2012 8:08:47 PM UTC+2, James Kuyper wrote:
    > #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.
     
    , Apr 26, 2012
    #4
  5. John Reye Guest

    I wrote:
    > 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;
    }
     
    John Reye, Apr 26, 2012
    #5
  6. John Reye Guest

    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 */
    }
     
    John Reye, Apr 26, 2012
    #6
  7. James Kuyper Guest

    On 04/26/2012 03:44 PM, wrote:
    > Thanks for those explanations and the code.
    >
    > On Thursday, April 26, 2012 8:08:47 PM UTC+2, James Kuyper wrote:
    >> #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.
     
    James Kuyper, Apr 26, 2012
    #7
  8. James Kuyper Guest

    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!
     
    James Kuyper, Apr 26, 2012
    #8
  9. John Reye Guest

    James Kuyper wrote:
    > "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.
     
    John Reye, Apr 26, 2012
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Suzanne Vogel

    variable num args via 'va_arg'

    Suzanne Vogel, Jul 5, 2003, in forum: C++
    Replies:
    2
    Views:
    452
    flekso
    Jul 5, 2003
  2. Gordon Burditt

    Re: va_arg() question

    Gordon Burditt, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    414
    Gordon Burditt
    Aug 7, 2003
  3. Eric Sosman

    Re: va_arg() question

    Eric Sosman, Aug 7, 2003, in forum: C Programming
    Replies:
    1
    Views:
    516
    Kevin Easton
    Aug 8, 2003
  4. Artie Gold

    Re: va_arg() question

    Artie Gold, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    433
    Artie Gold
    Aug 7, 2003
  5. Glen Herrmannsfeldt

    va_arg and short

    Glen Herrmannsfeldt, Nov 2, 2003, in forum: C Programming
    Replies:
    99
    Views:
    3,100
    James Kuyper
    Nov 24, 2003
Loading...

Share This Page