Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : pete
Date : Tue Oct 04 2005 09:31 am

robertwessel2@yahoo.com wrote:
> 
> Simo Melenius wrote:
> > Tatu Portin <axel86@mbnet.fi> writes:
> >
> > > Well, my problem here seems to be lack of good examples where
> > > recursion is needed. Would anybody provide some?
> >
> > Well, think of quicksort.
> >
> > As others have pointed out, you can generally simulate the effect of
> > recursion with a loop plus a stack. And that it's often a choice about
> > which-fits-best.
> >
> > But as an example, quicksort the algorithm is inherently of recursive
> > nature. It applies itself again to finish its own job -- that's just
> > the way it works. When programming quicksort it's definitely best
> > expressed as a self-recursive function, because that better reflects
> > its nature.
> >
> > The reader should feel free to try to implement an iterative quicksort
> > that's somehow "more iterative" than a straight-forward translation
> > into a loop that uses a stack/list to keep track of the boundary
> > indexes/nodes. That should help in seeing something, I hope.
> 
> While it's easy and obvious to express Quicksort in a fully recursive
> form (where both partitions are sorted recursively), the result is,
> unfortunately, unusable in the real world since you have potentially
> unbounded (OK, proportional to N) stack usage.
> 
> A partially recursive implementation, where the smaller partition is
> sorted with a recursive call and the larger one with an iteration,
> is a
> popular solution that avoids the complexity of an explicitly managed

#define BYTE_SWAP(A, B)                                     \
{                                                           \
    p1 = (A);                                               \
    p2 = (B);                                               \
    end = p2 + size;                                        \
    do {                                                    \
        swap  = *p1;                                        \
        *p1++ = *p2;                                        \
        *p2++ = swap;                                       \
    } while (p2 != end);                                    \
}

void q1sort(void *base, size_t nmemb, size_t size, 
           int (*compar)(const void*, const void*))
{
    unsigned char *left;
    size_t nmemb_right, middle, last, right;
    unsigned char *p1, *p2, *end, swap;

    left = base;
    while (nmemb-- > 1) {
        right = last = nmemb * size;
        middle = size;
        while (compar(left, left + middle) > 0 && middle != right) {
            middle += size;
        }
        while (compar(left + last, left) > 0) {
            last -= size;
        }
        while (last > middle) {
            BYTE_SWAP(left + middle, left + last);
            do {
                middle += size;
            } while (compar(left, left + middle) > 0);
            do {
                last -= size;
            } while (compar(left + last, left) > 0);
        }
        BYTE_SWAP(left, left + last);
        nmemb       =          last  / size;
        nmemb_right = (right - last) / size;
        if (nmemb_right > nmemb) {
            q1sort(left, nmemb, size, compar);
            left += last + size;
            nmemb = nmemb_right;
        } else {
            q1sort(left + last + size, nmemb_right, size, compar);
        }
    }
}

> stack as well as the explosive stack growth problem.

Similar logic as in the partially recursive implementation,
prevents explosive stack growth in the explicitly managed stack.

void q2sort(void *base, size_t nmemb, size_t size, 
           int (*compar)(const void *, const void *))
{
    unsigned char *left;
    size_t middle, last, right;
    struct {
        size_t bytes;
        void *base;
    } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;    
    unsigned char *p1, *p2, *end, swap;
 
    stack -> bytes = nmemb * size;
    stack -> base  = base;
    stack_ptr = stack + 1;
    do {
        --stack_ptr;
        if (stack_ptr -> bytes > size) {
            left = stack_ptr -> base;
            right = last = stack_ptr -> bytes - size;
            middle = size;
            while (compar(left, left + middle) > 0 && middle != right) {
                middle += size;
            }
            while (compar(left + last, left) > 0) {
                last -= size;
            }
            while (last > middle) {
                BYTE_SWAP(left + middle, left + last);
                do {
                    middle += size;
                } while (compar(left, left + middle) > 0);
                do {
                    last -= size;
                } while (compar(left + last, left) > 0);
            }
            BYTE_SWAP(left, left + last);
            if (right - last > last) {
                stack_ptr   ->  base = left + last + size;
                stack_ptr++ -> bytes = right - last;
                stack_ptr   ->  base = left;
                stack_ptr++ -> bytes = last;
            } else {
                stack_ptr++ -> bytes = last;
                stack_ptr   ->  base = left + last + size;
                stack_ptr++ -> bytes = right - last;
            }
        }
    } while (stack_ptr != stack);
}

-- 
pete

.