Antwort 1
~~~~~~~~
[ von Thomas Antoni, 21.10.2003 ]
Rekursion ist eine Programmiertechnik, bei er sich eine Befehlsfolge solange
selber aufruft bis eine Abbruchbedingung erfüllt ist. Die korrekte Formulierung
der Abbruchbedingung ist essenziell, weil das Programm sonst in einer
Unendlichkeitsschleife einfriert oder es zu einem Überlauf des Stapelspeichers
(Stack) kommt (siehe auch den FAQ-Eintrag "Fehlermeldungen und Fehlersuche -> Mein Programm bricht
mit "Overflow.." oder "Stapelplatz.." ab!"
).
Rekursion ist eine leistungsfähige Methode der Programmierung. Mit Rekursion
kann man alles das lösen, was sich durch Zergliederung eine Problems in immer
kleiner Schritte angehen lässt. Die Anwendung -> rekursiver Techniken
führt in derartigen Fällen oft zu kurzen, scheinbar einfachen und
übersichtlichen Programmen. Für viele Programmierer - ich gehöre leider auch
dazu - ist es aber sehr schwer, ein rekursives Programm nachzuvollziehen. Man
benötigt dazu eine bestimmte Art von Denken, die nicht jedem gegeben ist. Fehler
in rekusiven Programmen sind oft sehr schwer zu finden. Wenn Du Programme
schreiben willst, die gut "wartbar" sind und von anderen Personen gut
nachvollziehbar sind, solltest Du rekursive Techniken nur dann anwenden, wenn es
unvermeidbar ist
*** Rekursionen in QBasic
In QBasic-Programmen lagert man die rekursiv durchlaufenen Programmpassagen
meistens in -> Subroutinen oder -> Funktionen
aus. Im Gegensatz zu anderen BASIC-Dialekten unterstützt QBasick sehr wohl den
rekursiven Aufruf von SUBs und FUNCTIONs.
Ein einfaches Beipiel für Rekursion zeigt mein folgendes Programm RECURSE.BAS
, das die Zahlen von 1 bis zu einem wählbaren Wert k% miteinander addiert und
das Ergebnis anzeigt. Die einzelnen Additionen erfolgen in der SUB "recurse",
die sich sooft selbst aufruft bis alle Zahlen abgearbeitet worden sind.
'************************************************************
' RECURSE.BAS - Eine SUB ruft sich selbst auf ("Rekursion")
' ===========
' Dieses Q(uick)Basic-Programm demonstriert die rekursive
' Technik durch Addition aller Zahlen von 1 bis k%
' in der sich selbst aufrufenden Subroutine "recurse"
'
' (c) Thomas Antoni, 5.3.2004 - 8.2.2006
'************************************************************
'
DECLARE SUB recurse ()
'
COMMON SHARED k%, l%
'In Hauptprogramm UND in der SUB bekannte Variablen
CLS
INPUT "Gib k ein"; k%
CALL recurse
PRINT "Die Summe der Zahlen von 1 bis"; k%; " betraegt"; l%
SLEEP
'
SUB recurse STATIC
n% = n% + 1
l% = l% + n%
IF n% < k% THEN CALL recurse
END SUB
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online
unter www.antonis.de/faq/progs/recurse.bas
Das folgende Programm zeigt ein weiteres Beispiel für Rekursion:
'****************************************************************
' REKURS2.BAS = Demonstriert Rekursion mit Zeichnen von Quadraten
' ===========
' Dieses Q)uick)Basic-Pogramm demonstriert den rekursiven Aufruf
' von Subroutinen. Die SUB rek() zeichnet 4 Quadrate und ruft
' sich solange selbst zum Zeichnen verkleinerter und verschobener
' Quadrate auf bis die Seitenlaenge des Quadrats eine
' untere Grenze erreicht. Daurch erscheint auf dem Bildschirm ein
' interessantes grafisches Muster.
'
' (c) Thomas Antoni, 8.2.2006
' Nach einer Programmidee aus dem Buch
' "Frank Ostrowski und sein GFA-BASIC"
'****************************************************************
'
DECLARE SUB rek (x!, y!, r!)
'
COMMON SHARED faktor 'faktor als Globalvariable deklarieren (ist
'auch der SUB bekannt)
SCREEN 12
faktor = .5
CALL rek(300, 225, 115)
'
SUB rek (x, y, r)
LINE (x - r, y - r)-(x + r, y + r), , B 'Quadrat malen
IF r > 10 THEN
CALL rek(x + r, y, r * faktor) 'verschobene und ...
CALL rek(x, y + r, r * faktor) 'verkleinerte ...
CALL rek(x - r, y, r * faktor) 'Quadrate malen
CALL rek(x, y - r, r * faktor)
END IF
END SUB
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online
unter www.antonis.de/faq/progs/rekurs2.bas
Das bekannteste Beispiel für Rekursion ist der Sortier-Algorithmus
"QuickSort". Eine Beschreibung mit einem Programmbeispiel für QuickSort findest
Du im FAQ-Eintrag "Sortieren,
suchen und ersetzen -> Was gibt es für Sortieralgorithmen?" .
Ein in den Büchern gern zitiertes Beispiel für Rekursion ist die Berechnung
der Fakultät n! . Ein entsprechendes QBasic-Programmbeispiel findest Du im
FAQ-Eintrag "Zahlen verabeiten,
mathematische Probleme-> "Wie berechne ich die Fakultät n! einer Zahl n ?"
Weitere Beispiele und Informationen zur Rekursion in QBasic findest Du im
FAQ-Eintrag "Subroutinen und
Funktionen... -> Ich benötige umfassende Informationen über
SUBs/FUNCTIONs!" .
Answer 2
~~~~~~~~
[ by "Ask Doctor Jackson" - The QUIK_BAS List of Frequently Asked Questions
]
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
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.
Answer 3
~~~~~~~~~
[ from the Microsoft Knowledge Base ( www.microsoft.com ),
15.10.2001 ]
Towers of Hanoi: QuickBasic 4.50 Recursive SUBprogram
Example
*** SUMMARY
The Towers of Hanoi is a classic computer problem that has been used to
demonstrate the usefulness and ease of use of recursion. The following example
program shows how this problem can be solved with recursion in QuickBasic
Versions 4.00, 4.00b, and 4.50 for MS-DOS, Microsoft Basic Compiler Versions
6.00 or 6.00b for MS-DOS and MS OS/2, or Microsoft Basic PDS Version 7.00 for
MS-DOS and MS OS/2. QuickBasic versions earlier than Version 4.00 do not support
recursion.
*** MORE INFORMATION
The information below demonstrates the Towers of Hanoi problem.
If you have three towers (labeled A, B, and C, respectively) of equal height,
and you have "n" number of disks on Tower A, move the "n" disks from Tower A to
Tower C in the shortest number of moves.
Additional rules are as follows:
A larger disk cannot be placed on top of a smaller disk.
Only one disk can be moved at a time.
For each move, a disk must have one of the towers as a destination.
You will find through inductive proof that the shortest number of moves
required will be 2 raised to the n-1 power. The order of this algorithm (best
case) is O(2^n).
You will also notice that the only thing being kept track of on the three
towers is what is on top of each tower. The recursion of the program handles the
pushing and popping of the stack. Some implementations of the Towers of Hanoi
use a stack to keep track of what is on each tower.
The following is a code example:
(Remark by Thomas Antoni: The following program doesn't work on my computer
neither under QBasic 1.1 nor under QuickBASIC 4.5 using the Windows NT 4 OS)
DEFINT A-Z
DECLARE SUB HANOI(DISKS,TOWERA(),TOWERB(),TOWERC())
CLEAR ,, 4096
DIM TOWERA(2)
DIM TOWERB(2)
DIM TOWERC(2)
PRINT
PRINT" RECURSIVE TOWERS OF HANOI"
DO
INPUT "NUMBER OF DISKS? ", DISKS
PRINT
IF DISKS<>0 THEN
TOWERA(0)=1
TOWERB(0)=2
TOWERC(0)=3
PRINT
CALL HANOI(DISKS,TOWERA(),TOWERB(),TOWERC())
END IF
LOOP UNTIL DISKS=0
END
'
FUNCTION WHICHTOWER$(TOWER%)
SELECT CASE TOWER%
CASE 1: WHICHTOWER$=" A "
CASE 2: WHICHTOWER$=" B "
CASE 3: WHICHTOWER$=" C "
END SELECT
END FUNCTION
'
'
SUB HANOI (DISKS,TOWERA(),TOWERB(),TOWERC())
IF DISKS=1 THEN
DESTINATION$=WHICHTOWER$(BYVAL TOWERC(0))
SOURCE$=WHICHTOWER$(BYVAL TOWERA(0))
PRINT "MOVED DISK FROM"; SOURCE$;"TO";DESTINATION$
ELSE
CALL HANOI(DISKS-1,TOWERA(),TOWERC(),TOWERB())
DESTINATION$=WHICHTOWER$(BYVAL TOWERC(0))
SOURCE$=WHICHTOWER$(BYVAL TOWERA(0))
PRINT "MOVED DISK FROM"; SOURCE$;"TO";DESTINATION$
CALL HANOI(DISKS-1,TOWERB(),TOWERA(),TOWERC())
END IF
END SUB