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"
TABLE OF CONTENTS:
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
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
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
recurse
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]
DEFINT A-Z
SUB QuickSortSTR (Array() AS STRING, Low, High)
>>> Continued to next message
* OLX 2.1 TD * Post all questions in this box --> []
