Das deutsche QBasic- und FreeBASIC-Forum

[Revilo]

Hallo Leute,
hier mal eine fachliche Anfrage zu diesem Thema.

Rekursive Programmierung scheint ein sehr mächtiges "Werkzeug" zu sein.
Aber selbst das beste Werkzeug macht keinen Sinn, wenn man es nicht zu benutzen versteht. Mir geht es genau so.
Alle meine Programme habe ich bisher streng linear programmiert,
also eins nach dem anderen, Schritt für Schritt, Zeile für Zeile.
Bei komplexeren Problemen habe ich mich erwartungsgemäß schnell zwischen den ganzen nötigen Variablen komplett verzettelt.

Ich weiß nur grundsätzlich, daß sich bei rekursiver Programmierung eine Routine immer wieder selbst aufruft, bis eine bestimmte Abbruchbedingung erfüllt ist.
Aber:
Jeder erneute Aufruf ist eine zusätzliche "Bearbeitungsebene".
Das Ergebnis jeder einzelnen "Bearbeitungsebene" muß sich das Hauptprogramm ja irgend wie "merken".
Wenn z.B. 100 "Bearbeitungsebenen" nötig sind, geht der erforderliche Speicherbedarf doch wohl zwangsläufig "durch die Decke".
Oder ist das ein Trugschluß meinerseits?

Ich habe probeweise mal versucht, die Fakultät einer Zahl also (X!)
rekursiv zu bestimmen, bin aber mit "Pauken und Trompeten" gescheitert.
Ich hatte immer mit der Mitteilung "Speicherüberschreitung" zu kämpfen.

Offenbar habe ich das alles bisher niemals so richtig verstanden.
Vielleicht gab es auch einfach nur einen ganz kleinen Aspekt, den ich laienhaft nicht berücksichtigt habe. Keine Ahnung.

Kann mir jemand das rekursive Programmieren wirklich "wasserdicht" beibringen ? Welche fachlichen "Fallstricke" sollte ich dabei beachten?

Ist sicher eine anspruchsvolle Aufgabe, aber um so größer werden mein Dank und meine Anerkennung sein, wenn ich es endlich mal begriffen habe.

PS: Wann ist es überhaupt zweckmäßig, rekursiv zu programmieren?

Mit netten Grüßen Revilo

[nemored]

Aus Zeitgründen erst einmal nur eine kleine Teil-Antwort:

[dreael]

Vor langer Zeit geschrieben:

https://www.dreael.ch/Deutsch/BASIC-Knowhow-Ecke/SUB-Unterprogramme.html

Hier ansonsten auch ein Kapitel für Rekursion dabei. Falls Du FreeBasic verwendest:

https://www.freebasic-portal.de/befehlsreferenz/dir-197.html

Damit lassen sich bekanntlich Dateien in einem Verzeichnis als Schleife durchgehen. Passende Übung dazu: Operation

[nemored]

Das rekursive Durchsuchen des Verzeichnisses ist übrigens ein sehr gutes Beispiel, wo Rekursion sinnvoll ist. Überhaupt jede Art von Tiefensuche - beispielsweise werden Spielzugberechnungen eines Computerspielers häufig rekursiv gemacht.
Mein Laser-Spiel arbeitet auch mit Rekursion. Es gibt für den Laserstrahl eine Funktion zur Wegberechnung; und wenn der Laserstrahl auf einen Spiegel trifft, der ihn auf zwei Wege aufteilt, wird wiederum zweimal diese Funktion aufgerufen.
Eine Reihe von Sortieralgorithmen arbeiten ebenfalls rekursiv (divide et impera)

Noch ein paar nachgeschobene Antworten:

[Revilo]

Hallo nemored,
du erscheinst mir als sehr kompetent. Deshalb verzeih mir bitte, wenn ich mich erneut an dich wende, um deinen Rat zu erbitten.
Ich bin immer noch dabei, ein Programm zu schreiben, das Sudokus sauber löst. Mir wurde geraten, es erstmal auf klassischem Wege zu versuchen.
Laut Internet gibt es aber über 40 Lösungsverfahren.
Alle müssten erst mal programmiert werden, um als "Lösungs-Werkzeug" verfügbar zu sein. Man kann ja nie wissen, wann welches "Werkzeug" wirklich mal nötig wird. Das erscheint mir als kaum zu bearbeitende Lebensaufgabe.

Deshalb versuche ich, mich mit der Rekursion (Backtracking) anzufreunden.
Scheint ein sehr effektives Verfahren zu sein.

Man muss allerdings beim Backtracking unterscheiden, ob es weiter geht oder ob man in einer "Sackgasse" gelandet ist.
In vielen Programmiersprachen gibt es dafür die Begriffe "True" und "False".
Leider aber nicht in Q-Basic. Da die Rekursion aber auch in Q-Basic möglich sein sollte, muss es also eine Art Umschreibung für True und False geben, die dieselbe Wirkung wie True und False hat.
Kannst du mir dabei irgend wie weiterhelfen?

Wie müsste ich in Q-Basic eine Abbruchbedingung programmieren, um einen
Speicherüberlauf zu vermeiden?
Dass ich immer auf einen Speicherüberlauf hingewiesen werde ist eines der größten Probleme, die ich mit der Rekursion habe.


Mit netten Grüßen Revilo

[nemored]

In Sprachen, die True und False nicht selbst bereits implementiert haben, verwendet man üblicherweise True = -1 und False = 0 (das hat was mit der Binärcodierung der Zahlen und mit den Bit-Operatoren zu tun). Du kannst einfach am Anfang des Programms ein

[Revilo]

Hallo nemored,
vielen Dank für deine Mail.
Wenn ich sie richtig verstanden habe, sind "True" und "False" also keine
Boolians, wie etwa "and", "or" oder "xor", sondern "stink-normale" Variablen, die laut Spielregeln mit -1 für "True" und 0 für "False" zu belegen sind.
Offenbar könnte ich sie also ebenso gut, der deutschen Sprache gemäß "wahr" und "falsch" nennen, oder "Fritz" und "Franz".
Hauptsache, ich belege "wahr" mit -1 und "falsch" mit 0.
Oder eben "Fritz" mit -1 und "Franz" mit 0. Richtig?
Wenn dem so ist, hast du mich gerade von der Zwangsvorstellung befreit,
dass "true" und "false" Boolsche Ausdrücke sind.

Dass "true" mit -1 zu belegen ist, nehme ich mal als "Spielregel" so hin.
Aber es macht mich schon neugierig, warum true = 1 nicht den selben Effekt erfüllen sollte.
Du hattest ja sinngemäß geschrieben, dass dies mit der Binär-Mathematik
zu tun hat. Die binäre Addition ist mir noch geläufig. Subtraktion, Multiplikation und Division müsste ich noch mal nachlesen, weil schon lange nicht mehr angewendet. Da bin ich etwas aus der Übung.
Gelernt habe ich sie alle aber mal.

Gruß Revilo

[Berkeley]

[nemored]

Ergänzend dazu:
Der Ganzzahl-Wert 0 bedeutet speichertechnisch, dass alle Bit den Wert 0 besitzen. NOT 0 bedeutet dementsprechen, dass alle Bit den Wert 1 haben. Eine Ganzzahl, bei der jedes Bit gesetzt wird, stellt wiederum den Wert -1 dar (Stichwort Zweierkomplement). Daher ist die Belegung FALSE = 0 logisch und TRUE=-1 sehr naheliegend. Aber letztlich gibt es in FreeBASIC aus historischen Gründen keine echten boolschen Werte - und in QBasic schon gar nicht.

(Um es auf die Spitze zu treiben: Selbst in "IF a<10 AND c<>0 THEN" arbeitet QBasic/FreeBASIC nicht mit boolschen Ausdrücken, sondern verknüpft die resultierenden Vergleichswerte "-1" und/oder 0 bitweise. Du kannst gern mal ausprobieren, was 5*(3<8)-(4>0) ergibt. Ein früherer Kollege von mir erzählte mir mal, dass er gern auf diese Art und Weise programmiert hat.)
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

[Berkeley]

Ich neige gerne zu der C-typischen Kurzschreibweise z.B. "IF c THEN" statt "IF c<>0 THEN", das kann dann allerdings in die Hose gehen wenn man z.B. schreibt "IF c AND a<10 THEN" ;-)

Erklärung: es gibt eben ein logisches und ein bitweises AND, bei IF will man normal das logische, in dem Fall führt der Compiler aber c AND a aus, hält es für eine "Berechnung", dessen Ergebnis auf <10 geprüft wird.

Wenn man nachdenkt, dann gibt's ja eigentlich gar keinen Boolean-Typ in der Maschinensprache. Jede CPU hat aber zumindest einen (schnellen) Befehl, um zu ermitteln, ob ein Register(Variable) 0 ist. Und das nutzt man eben auch normal für Boolean. Es gibt auch nur Befehle für 8 Bit Operationen, aber selten nur für 1 Bit. Zumindest wird man also ein Byte für Booleans nehmen, und dann ist es definitiv besser, wenn man -1 für TRUE verwendet - was unsigned bei 8 Bit 255 entspricht, bei 16 Bit 65535 und bei 32 Bit 4294967295... (bei signed alles immer -1)

[grindstone]

Das ist doch ganz einfach: 0 ist FALSE, alles andere ist TRUE.

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!

[Berkeley]

[nemored]

Gibt halt trotzdem Probleme, wenn man einen Nicht-Null-Wert mit einem anderen Nicht-Null-Wert AND-verknüpft und ein TRUE erwartet, aber ein FALSE herauskommt. Bei einer Flag-Prüfung verwende ich eher

[Revilo]

Hallo Leute,
vielen Dank für eure helfenden Beiträge.
Ich habe versucht euch eine Antwort zu schreiben.
Daran habe ich über 1 h lang "gefeilt".

Manchmal klappt das Senden einer Antwort, manchmal nicht.
In diesem Fall klappte es nicht.
Offenbar war hier etwas anders, als bei den gelungenen Fällen.
Leider weiß ich nicht, was anders war.
Von einem Münzwurf kann das ja wohl kaum abhängen.

Daher meine Frage:
Was muss ich machen, welche Einstellungen sind nötig, um sicherzustellen, dass eine von mir verfasste Antwort auch tatsächlich bei euch ankommt?
Offenbar bin ich mit dem Handling hier noch nicht so ganz vertraut.

Gruß Revilo

[grindstone]

Einfach so lange probieren, bis es klappt.

Und speziell längere Texte vor dem Absenden vorsichtshalber in die Zwischenablage kopieren (Strg+A Strg+C). Das spart im Ernstfall eine Menge Arbeit.

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!

[Berkeley]

Mit hoher Wahrscheinlichkeit hast du irgendwas aktiviert das Cookies blockiert. Ansonsten gibt's zwar hier nen Session-Timeout (trotz dauerhaftem Login), aber anders als bei anderen Foren verschwindet glaub' ich bei mir der Text nicht, wenn dann das Abschicken mal nicht klappt. - Man muss wohl einfach nur zurückblättern zum Eingabeformular. Bei anderen Foren muss man natürlich daran denken, sein Posting zu markieren, kopieren, und danach erst zu posten. Beim ersten Versuch gibt's dann einen Fehler - weil man "ausgeloggt" ist, beim zweiten Versuch hat man dann wieder ne gültige Session, und das Posten klappt.

[Revilo]

Hallo Leute,
hier nochmals meine "verloren gegangene Mail".
Wenn man eine Zahl in ein Sudoku einträgt, muss sie in der jeweiligen Zeile, Spalte und im Block ausgeschlossen werden, sonst würde man gegen die Sudoku-Regeln verstoßen.
So ist es zumindest, wenn man es klassisch programmieren möchte.

Ist dieses "ausschließen" bei rekursiver Programmierung auch nötig oder fällt es praktisch weg, weil es ja ein ganz anderer Programmier-Ansatz ist?

Wenn es doch nötig ist, habe ich folgende Frage:
Backtracking heißt ja letztlich probieren. z stehe dabei für die Zeile, s für die Spalte und w für den zu probierenden Wert.
Momentan arbeite ich jeweils mit der Zelle(z, s, w).

Diese kann für den Wert w drei Zustände annehmen:
Zelle(z, s, w) = 1 w absolut sicher feststehend (z.B. Ersteinträge)
Zelle(z, s, w) = -1 w absolut sicher ausgeschlossen
Zelle(z, s, w= = 0 w weder noch, also weiterhin möglich

Wenn ich in Zeile z und Spalte s den Wert w ausprobiere, setze ich also
Zelle(z, s, w) = 1 als vermeintlich richtig und sicher gefunden.
Der Wert w muss dann in Zeile z , in Spalte s und im Block um z, s
ausgeschlossen werden (Sudoku-Regeln).

Dieses vermeintlich richtige w führt in den folgenden Zellen zu weiteren Einträgen, die jeweils auch zeilen-, spalten- und blockweise ausgeschlossen werden müssen.

Zum Beispiel 20 Zellen später, stelle ich fest, dass ich in einer Sackgasse gelandet bin, es also nicht mehr weiter geht.

Die ursprüngliche Vermutung, w sei richtig, hat sich also als falsch erwiesen.
Wie mache ich alle dadurch generierten Zeilen-, Spalten- und
Block - Ausschlüsse wieder rückgängig, ohne einen einzigen zu vergessen bzw. zu übersehen, denn sie waren wegen der falschen Annahme von w ja gar nicht berechtigt, ausgeführt zu werden?

Oder ist diese ganze Mühe wegen des Backtracking-Verfahrens gar nicht mehr nötig?

Gruß Revilo

[nemored]

Ich verweise dazu auf meine Antwort vom 01.11.2024, 02:42 Uhr:

[Revilo]

Hallo Nemored,
du schreibst: Das brauchst du nicht. Die Ersteinträge stehen zu Beginn im Array, alle anderen Werte sind bis zum Schluss aus der Kathegorie "möglicherweise richtig".

Ich hätte das auch gern als Zitat angegeben, so wie du es machst. Leider
weiß ich nicht, wie das geht. deshalb habe ich es klassisch mit Strg +C
und Strg +V gemacht.

Ein Array ist wohl eine Art Tabelle, in deren Zeilen und Spalten die Ersteinträge erfasst werden. Da ich aber auch nicht weiß, wie man in
Q-Basic eine solche Tabelle darstellt, arbeite ich mit einem String der
Länge 81. Ich nenne es Urwort$.

Zu Anfang steht an jeder Stelle dieses Urwortes eine "0" (als String, nicht als numerischer Wert). Also Urwort$ ="0000000000...."
Für jeden Ersteintrag bestimme ich aus der Zelle(z, s), in der er stehen soll,
seine Stelle im Urwort$ . Stelle = (z-1)*9 + s.
Über die MID$ -Funktion trage ich so jeden Ersteintrag an der ihm zustehenden Stelle ein.

So entsteht schließlich das Sudokuwort$, das - wie eine Tabelle - den
Startzustand darstellt, nur halt in Form eines Wortes mit 81 Zeichen.

Um diese Ausgangswerte nicht versehentlich zu überschreiben, bilde ich ein
weiteres Wort. Dieses nenne ich Loeswort$.
Zu Anfang ist es eine exakte Kopie des Sudokuwortes.

Loeswort$ = Sudokuwort$

Hierin werden mit der MID$-Funktion sämtliche Folgeeinträge und deren eventuelle Korrekturen vorgenommen.

Bei erfolgreicher Lösung gibt es im Loeswort$ keine "0" mehr.
Alle Zellen (z, s) haben dann einen Wert > 0.

Ob dem so ist, frage ich über die INSTR-Funktion regelmäßig ab.
Wenn als Rückgabewert dieser Funktion eine 0 erscheint, ist das Sudoku gelöst. Alle Einträge sind richtig getätigt.

Im Q-Basic-Syntax muss das Ergebnis dieser Abfrage an eine Variable
übergeben werden etwa, wie folgt:

a= instr(1,Loeswort$,str$(0))

a=0 hieße dann, keine Null gefunden, Rätsel gelöst

a <> 0 hieße dann, noch nicht gelöst, Suche muss fortgesetzt werden.

Muss es deshalb nicht auch für True und False einen Ort (eine Variable) geben, wohin sie übergeben werden?

Und erst nach dem, was in dieser Variablen dann steht, wird entschieden, wie es weitergehen muss, also ob ein weiteres Backtracking nötig ist oder eben nicht mehr.

Nach meinem bisherigem Verständnis gibt es aber keine Variable, an die
True bzw. False übergeben werden könnte. Hängen True und False da nicht irgendwie, irgendwo in Luft?
Wie ist es dann möglich, dass sie trotzdem verarbeitet werden?

Du schreibst ferner:
Du setzt ja zunächst einmal die Zahl (vorläufig) ein und rufst dann rekursiv erneut den Backtracking-Algorithmus auf. Wenn als Rückgabe zurückkommt "funktioniert nicht", löscht du die Zahl wieder und probierst die nächste. Dass das in den anderen 20 Zwischenschritten ebenfalls passiert, erledigt die Rekursion.

Da frage ich mich wie?
Muss das zuvor irgendwie programmiert werden, damit es funktioniert?
Wie findet die Rekursion möglicherweise 50 falsche Ausschüsse wieder, um sie rückgängig zu machen? Das ist für mich immer noch ein großes Mysterium.

Im Internet werden Sudoku-Solver im Python-Code vermittelt.
Damit kann ich leider nichts anfangen, weil ich nur in Q-Basic halbwegs zurechtkomme.

Mir ist aber aufgefallen, dass es dort auch den return-Befehl gibt.
Return False oder Return True, je nach dem.
Und damit bin ich wieder bei meiner Frage: "Wohin, an welche Variable, werden True bzw. Flase denn übergeben?

Den Befehl Return kenne ich in Q-Basic nur als Abschluss einer
GOSUB-Anweisung. Man kehrt dann zurück zu der Stelle, wo GOSUB aufgerufen wurde.

Ist dieses Python - Return, dasselbe Return, das ich von Q-Basic kenne?
Ist das im Grunde eine ineinander verschachtelte GOSUB-Anweisung?

Hier geht bei mir fachlich also noch vieles kreuz und quer durcheinander.
Auf deutsch: Keine Ahnung.

Ich sende dir einfach mal den Python-Code, den ich gefunden habe.
Wahrscheinlich kannst du damit eher etwas anfangen, als ich.
Es wäre toll, wenn du ihn mir in Q-Basic "übersetzten" könntest.

Python-Code:
def backtracking(Sudoku):
'Sudoku steht dabei offenbar für die Tabelle der Ersteinträge
'Schließlich muss man dem Rechner ja erst mal sagen, was die Aufgabe
'ist, die er lösen soll.
'Das wäre wohl das Äquivalent zu meinem Loeswort$.
if alle_Felder_ausgefüllt (Sudoku):
'das wäre praktisch meine INSTR-Abfrage, ob es noch eine "0" gibt.
return True

Zeile,Spalte = nächstes_freies_Feld (Sudoku)

for Zahl in range(1,10):

If Zahl_erlaubt(Zeile,Spalte,Zahl):
'das wäre wohl die Abfrage, ob eine Zahl bereits vorhanden, also
'quasi schon ausgeschlossen ist.
'Dann darf sie natürlich nicht ein weiteres mal eingetragen werden

Sudoku [Zeile][Spalte] = Zahl
'Hier würde dann wohl meine MID$-Funktion zum Eintragen
'Anwendung finden.

gelöst = backtracking(Sudoku)

If gelöst:
return True

Sudoku[Zeile][Spalte] = 0
'Hier würde dann wohl meine MID$-Funktion zum Rückgängig
'machen Anwendung finden.

return False

------ Python -Code Ende ---

Abschließend für heute nur noch eine Frage:
Backtracking ist ja ein immer wieder ablaufendes Verfahren, das entsprechend oft, je nach Notwendigkeit, aufgerufen werden muss.

Kann man das nicht auch mit einer Do - Loop - Schleife lösen?
Wenn meine INSTR -Abfrage den Wert 0 ergibt, gibt es eben keine "0" mehr im Loeswort$. Dann sind alle Werte korrekt eingetragen. Kann man da nicht auch einfach "exit do" eingeben, und fertig ist die Laube?

Anders gefragt: Was ist der Unterschied zwischen DO-Loop und Rekursion?
Wahrscheinlich ist die Rekursion schneller. Ist das der einzige Aspekt, weshalb Rekursion hierbei vorzuziehen ist, oder gibt es noch weitere?

Gruß Revilo

[Berkeley]