Quik_Bas Faq2.1 1/

 BBS: Inland Empire Archive
Date: 03-28-93 (21:04)             Number: 244
From: QUINN TYLER JACKSON          Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: Quik_Bas Faq2.1       1/       Conf: (2) Quik_Bas
                                QUIK_BAS FAQ2.1

        *                                                              *
        *                    "Ask Doctor Jackson"                      *
        *     The QUIK_BAS List of Frequently Asked Questions with     *
        *             Some Simple Public Domain Solutions              *
        *                                                              *

                                Written by
                            Quinn Tyler Jackson
                      The QUIK_BAS "Keeper of the FAQ"
                                with source
                               samples  from
                             "Various Sources"


        q1.0    The BASICS of BASIC
                s1.0    QUIKSORT.BAS    -- recursive quicksort SUB

        q2.0    Commonly Requested Routines
                s2.0    HUTHSORT.BAS    -- iterative quicksort SUB
                s3.0    BISEARCH.BAS    -- binary search FUNCTION

        q3.0    Advanced Topics         -- "Hashing in QuickBASIC"
                t1.0    Hashing Collision Table
                s4.0    FSTPRIME.BAS    -- generates 4K+3 prime number
                t2.0    List Management System Ratings
                s5.0    WORDHASH.BAS    -- word distribution counter

        q4.0    Structured BASIC Techniques

NOTE:   Neither Quinn Tyler Jackson nor his company, JackMack Consulting
        & Development accepts responsibility for the soundness of the
        following advice.  Certain pieces of other people's public domain
        code has been spliced into this FAQ for purely demonstrative
        purposes, and it is by no means to be assumed that Quinn Tyler
        Jackson is claiming ownership of such pieces of source code.
        All source remains the property of those who originally wrote it,
        as understood by Canadian, American, and International Treaty.

        The text portion of this file itself is hereby released into the
        "Public Domain" for the purposes of education and enlightenment.

Q1.0    The BASICS of BASIC:

Q1.4    Okay, Quinn, I've figured out FUNCTIONs and SUBs, and have even
        started using them with some kind of skill.  Now, thing is, I
        come up to this thing called 'recursion.'  What's this all about,
        and can you show me some practical application of it?

A1.4    There is an old joke about the cryptic nature of dictionaries that
        goes something like this:

        re'CUR'sion (noun) 1. see recursion

        Actually, that's a pretty sad joke.  One computer scientist's
        definition states:

        "... a recursive algorithm is one that contains a copy of itself
        within one of its instructions.  Thus, a recursive algorithm is
        reminiscent of a set of mirrors in which you can see yourself
        looking at yourself looking at yourself."  [J. Glenn Brookshear]

        Recursion is a powerful programming tool, and any comprehensive
        programming language allows it.  QuickBASIC and its dialects are
        no exception.  A simple example of recursion:

        SUB recurse
        END SUB

        This thing will go in circles until the stack is full, crashing
        the program should it ever be called.  It illustrates two of the
        main pitfalls of recursion:

                1. recursion in QuickBASIC eats the stack for breakfast
                2. there must be a terminating condition to exit the loop

        Since each call to a SUB or FUNCTION does some pushing to the
        stack, it must always be remembered that recursive routines will
        require a bit of the stack for every instance they are called.
        It is sometimes hard to know in advance how many times a recursive
        routine will end up calling itself, and therefore, one cannot
        know with any accuracy how much a given recursive routine will
        decide to rob from the stack.  Be warned!

        This also leads to the next issue: there must ALWAYS be a
        terminating condition to exit the loop.  Sometimes it is easy to
        overlook this point.  Consider the above simple example.  It
        never stops calling itself, does it?  Were a theoretical computer
        to exist that had a theoretically infinitely large stack that could
        never be consumed by even the deepest level of recursion, what
        happens if that routine goes off into a corner and keeps calling
        itself?  It results in a permanent time out known as a crash.
        (The moral of this?  A bug on a i486 system is still a bug, just
        a bug that happens sooner.)

        An example of a terminating condition added to the above code:

        SUB recurse(n%)
        n% = n% + 1
        IF n% < 10 THEN
        END IF
        END SUB

        This SUB will call itself only until n% is equal to ten, at which
        point, it will reach its terminating state, and be finished on its
        job.  This is a simple example, I admit, but NEVER forget to
        include a terminating statement in your recursive routines, or
        you will pay for it with a crash.

        Now that we have that out of the way, let's kill two birds with one
        stone.  (It could be argued, in fact that the act of killing two
        birds with only one stone probably involves recursion somewhere in
        the solution.)  Everyone wants to know a good QuickSort algorithm,
        and most implementations of that use recursion.  So, a modified
        version of the QuickSort SUB from Microsoft, one that sorts
        an array passed to it:

S1.0    QUIKSORT.BAS [F210S01.BAS]

SUB QuickSortSTR (Array() AS STRING, Low, High)
'            /^\              /^\
'             |                |
'    Change these to any BASIC data type for this routine to
'    handle other types of data arrays other than strings.
'============================== QuickSortXXX ================================
'  QuickSortXXX works by picking a random "pivot" element in Array(), then
'  moving every element that is bigger to one side of the pivot, and every
'  element that is smaller to the other side.  QuickSortXXX is then called
'  recursively with the two subdivisions created by the pivot.  Once the
'  number of elements in a subdivision reaches two, the recursive calls end
'  and the array is sorted.

'            Microsoft's source code modified by Quinn Tyler Jackson
>>> Continued to next message

 * OLX 2.1 TD * Post all questions in this box --> []
Outer Court
Echo Basic Postings

Books at Amazon:

Back to BASIC: The History, Corruption, and Future of the Language

Hackers: Heroes of the Computer Revolution (including Tiny BASIC)

Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Scientists and Iconoclasts who were the Hero Programmers of the Software Revolution

The Advent of the Algorithm: The Idea that Rules the World

Moths in the Machine: The Power and Perils of Programming

Mastering Visual Basic .NET