From: halderen@fwi.uva.nl (Berry van Halderen (I88))
Subject: Re: A LITTLE BRAINTEASER...
Organization: FWI, University of Amsterdam
Date: Fri, 14 Aug 1992 12:30:54 GMT

aet@mullian.ee.mu.OZ.AU (bert thompson) writes:

>hi!
>i have a small problem that's been bugging for a while now.
>here's a program that reverses input from the keyboard:

>main()
>	char ch = getchar();
>	if (ch == EOF)
>		;
>	else {
>		main();
>		putchar(ch);
>	}
>}

>the interesting thing about the program is that it uses no data structures
>(structs, arrays, pointers, etc..), to do its thing. everything is thrown
>on the stack.
	[stuff deleted]
>is it possible to write a program that reverse the order of input lines
>without using data structures.
>i.e.
>  the
>  quick
>  brown
>becomes:
>  brown
>  quick
>  the
>the rules of the game are you can use anything but data structures, or more
>specifically you cannot use the heap.
>i think it can be done, but i can't figure out how.
>(use of a few mutually recursive functions i think is the go.)
>anyone got an idea??


The solutions so far posted were or: totally incorrect, did use datastructures
(translating pascal ain't no good coz strings are datastructures) or we're
hacking around on the stack. This can lead to porting problems.
ANSI-C and most Classic C compilers do provide variable number of arguments.
Using this, I think I have found a solution that is cleaner. Dirty still.
The program:

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdarg.h>
    
    void rwline(    int lastchr,...);
    void printline( va_list ap);
    
    void
    printline(va_list ap)
    {
     va_list next;
     int c;
            c = va_arg(ap, int);
            if(c) {
                    next = va_arg(ap, va_list);
                    printline(next);
                    putchar(c);
                    }
    } /* printline() */
    
    void
    rwline(int lastchr,...)
    {
     va_list ap;
     int c;
            c = getchar();
            if(c==EOF) {
                    return;
            } if(c!='\n') {
                    va_start(ap,lastchr);
                    rwline(c,lastchr,ap);
                    va_end(ap);
            } else {
                    rwline(0);
                    if(lastchr) {
                            va_start(ap,lastchr);
                            printline(ap);
                            va_end(ap);
                            putchar(lastchr);
                            }
                    putchar('\n');
                    }
    } /* rwline() */
    
    int
    main(int argc, char *argv[])
    {
            rwline(0);
    } /* main() */

It works. It implicitly builds a linked list into the stack. There are
no pointers (well, ap is a pointer in most implementations) structs or
whatever, and no calculation of stack addresses is done (which is cleaner).

If you don't even want a implicit list like this to be build, but want to
work pure recursively: It cannot be done!
Prove? Neh, I don't want to prove it, but after a sleepless night I'm quite
certain. I do however think it can be done if you know the number of
characters per each line before reading each line.

A different remark: DONT use main functions recursively! Some compilers
rely on this. I even believe that in the C definition it says that you
may not call the main() function from any routine. It is also bad
programming!

			Berry
-- 
/* The future isn't as good          / / Only    Berry A.W. van Halderen    */
/*   as it has been.                / / Amiga    Email: halderen@fwi.uva.nl */
/* It's my opinion and          \ \/ / makes it                             */
/*   I share it                  \ \/ possible   University of Amsterdam    */