Prolog Rekursion?

Hallo,

ich bin gerade dabei Prolog zu lernen, komme aber bei der Rekursion nicht weiter, ich verstehe einfach nicht wie das genau abläuft, wenn ich z.B.:

zahl(0).

zahl(plusEins(X)) :- zahl(X).

in meiner Datenbasis stehen hab. Warum weiß dann Prolog, dass

zahl(plusEins(plusEins(0))) true ist?

wenn man für X = 0 hat ist ja zahl(0) und somit durch Implikation der Term zahl(plusEins(0)) auch erfüllt. Aber warum soll dann zahl(plusEins(plusEins(0))) auch erfüllt sein?

1 Antwort

magicced01

03.07.2023, 23:17

Die Magie der Rekursion in Prolog (und in der Informatik allgemein) liegt in der Fähigkeit, die gleiche Logik auf immer kleinere Teile eines Problems anzuwenden, bis man einen Zustand erreicht, den man direkt lösen kann - diesen Zustand nennt man Basisfall oder Basisfälle.

In Ihrem Beispiel ist `zahl(0).` der Basisfall. Dieser gibt an, dass `0` eine Zahl ist.

Die rekursive Regel `zahl(plusEins(X)) :- zahl(X).` bedeutet so viel wie "Wenn X eine Zahl ist, dann ist `plusEins(X)` auch eine Zahl". In diesem Sinne "erweitert" es das, was als "Zahl" definiert ist, über den Basisfall hinaus.

Wenn Prolog nun gefragt wird, ob `zahl(plusEins(plusEins(0)))` eine Zahl ist, geht es folgendermaßen vor:

1. Es überprüft, ob es diese Behauptung direkt in seiner Datenbank (den Fakten und Regeln, die es kennt) finden kann. In diesem Fall kann es das nicht.

2. Da es die Behauptung nicht direkt finden kann, sucht es nach einer Regel, die passen könnte. Es findet die Regel `zahl(plusEins(X)) :- zahl(X).`

3. Es versucht, die Regel anzuwenden, indem es `X` mit `plusEins(0)` ersetzt (das ist das, was übrig bleibt, wenn man von `plusEins(plusEins(0))` das äußerste `plusEins(...)` entfernt).

4. Nun muss es überprüfen, ob `zahl(plusEins(0))` wahr ist. Wieder kann es diese Behauptung nicht direkt finden, also wendet es die Regel erneut an, diesmal ersetzt es `X` mit `0`.

5. Jetzt muss es überprüfen, ob `zahl(0)` wahr ist. Diesmal kann es die Behauptung direkt in seiner Datenbank finden, da `zahl(0).` ein Fakt ist, den Sie definiert haben. Also ist `zahl(0)` wahr.

6. Da `zahl(0)` wahr ist, folgt daraus (gemäß der Regel), dass `zahl(plusEins(0))` wahr ist.

7. Und da `zahl(plusEins(0))` wahr ist, folgt daraus (wieder gemäß der Regel), dass `zahl(plusEins(plusEins(0)))` wahr ist.

In diesem Sinne "arbeitet" sich Prolog von innen nach außen durch die verschachtelten `plusEins(...)` Aufrufe, bis es beim Basisfall `0` ankommt. Dann arbeitet es sich zurück und bestätigt, dass jeder der darüberliegenden Aufrufe auch wahr ist, weil der darunter liegende wahr ist.

Das ist das grundlegende Prinzip der Rekursion in Prolog. Es ist ein wenig gewöhnungsbedürftig, wenn man es das erste Mal sieht, aber mit etwas Übung wird es klarer und beginnt Sinn zu machen. Es ist eine sehr mächtige Technik, die es ermöglicht, viele Probleme auf sehr elegante Weise zu lösen.

J2D3G

Fragesteller

03.07.2023, 23:45

Danke danke, das hat mir gerade sehr geholfen, super erklärt :3

Ähnliche Fragen

Term aufstellen, wie?

Hallo, ich verstehe solche Aufgaben wie z.B. „Das Dreifache einer Zahl, vermehrt um 7“ einfach nicht. Kann jemand mir sagen, wie man so etwas löst und was für einen Term man aufstellen muss? Danke im Voraus:)

...zur Frage

Arduino: Wie wird hier die Quersumme berechnet?

Ich habe hier den folgenden Teil eines Sketches:

byte Qsumme(int Zahl)
{
  byte Ergebnis = 0;
  
  while (Zahl > 0) {
    Ergebnis = Ergebnis + Zahl % 10;
    Zahl = Zahl / 10;
  }

  return Ergebnis;
}

Die Funktion soll die Quersumme der Zahl ausrechnen. Z.B.: 503 wird zu 8.

Ich verstehe jedoch nicht, wie das hier abläuft. Könnte mir das jemand erklären?

MfG

...zur Frage

Verstehe Mathe gerade nicht. Was sind 2,4c:0,8c? Man soll den Term vereinfachen.?

Eigentlich sollte das doch 3 ergeben ganz einfach. Aber wenn ich jetzt das c durch eine Zahl ersetzte und im Taschenrechner eingebe kommt was anderes raus. Wenn man den Term bei einem Term Vereinfacher eingibt kommt auch nicht 3 raus. Eigentlich muss man ja erst 2,4 mal c dann durch 0,8 und zum Schluss mal c rechnen. 3 würde aber nur rauskommen wenn man 2,4 mal c in den Zähler eines Bruchs und 0,8 mal c in den Nenner tut.

...zur Frage

Prolog: Wann ist false auch eine Lösung?

Hallo,

manchmal gibt mir Prolog false und manchmal nicht. Ich hatte es so gelernt: ,,ist es nicht definiert dann ist es für Prolog false". Aber dann habe ich diesen Fall:

p(a,b).
p(a,c).
p(d,e).
p(d,f).
p(g,f).
q(h).
q(i).
q(j).
r(h, a).
r(i, d).
r(j, g).
s(X,Y,Z):- q(X), r(X, Y), p(Y, Z).

Das Query dazu ?- s(X,Y,f). Ersetzt man X mit h erhält man ?-r(h,Y),p(Y,f). Wenn ich jetzt Y ersetze mit a dann hätte ich erwartet, dass der mir false rausgibt da p(a,f) nicht definiert ist, aber er "failed" und sucht weiter. Die Lösungen sind X=i, Y=d und X=j, Y=g. Würde man als Query ?- p(a,f). eingeben erhält man false.

Ein anderes Beispiel wo false rauskommt:

append ( [] , L , L ) . 
append ( [H|T1] , L2 , [H|T3]) :- append (T1,L2 ,T3)

Mit dem Query ?-append(X,X,[ ]). Lösungen sind X=[ ];false.

Bei beiden Beispielen hatte ich intuitiv die richtigen Lösungen raus. Nur würde ich jetzt gerne wissen wo der Unterschied besteht..

Schonmal vielen Dank:))

...zur Frage

Warum kennen so wenige Informatiker die Programmiersprache Prolog aus eigener Erfahrung?

Warum hat die Sprache eine so geringe Bekanntheit? Gibt es einen Ersatz dafür? Das Konzept ist doch praktisch.

...zur Frage

Ich brauche dringend Hilfe bitte, denn ich verstehe die Frage nicht?

Gib einen Term mit einer variablen n an, der für jede natürliche Zahl, die man für n einsetzt,

a) das doppelte Quadrat der Zahl,

b) die Hälfte von der Hälfte der Zahl,

c) ein um 5 vermindertes Drittel der Zahl liefert.

...zur Frage

Kann mir jemand diese Aufgabe erklären?

Ich verstehe diese Aufgabe nicht.

Valentin denkt sich zwei Zahlen. Er addiert das 5-Fache der Summe der beiden Zahlen zum Quadrat der ersten Zahl. Stelle einen Term für Valentins Rechnung auf.

...zur Frage

Hilfe in Mathe?

Also man soll einen term aufstellen anhand von Wörtern oder so was eben

Aufgabe:

Subtrahieren das Quadrat der Zahl s von der Summe der Zahlen r, s und t.

Könnt ihr mir helfen und mir den Term schreiben? (vllt. verstehe ich es dann)

Bedanke mich jetzt schonmal ✌🏻

Habs gecheckt DANKEEE

...zur Frage

Pi ist unendlich und kann jede Zahl beinhalten?

Hallo,

Da Pi unendlich, müsste Pi ja jede Zahl die existiert beinhalten können. Somit müsste es auch die Zahl 1 mit unendlich Nullen beinhalten oder ? Wenn dass so ist wäre ja kein Platz für die anderen Zahlen mehr oder verstehe ich da etwas falsch ?

Vielen Dank für die Antworten OpticalTaco1.

...zur Frage

Sieb des Eratosthenes in Golang?

Hallo,

mein Informatik-Lehrer hat uns eine Aufgabe gegeben, die wie folgt heißt:

Funktionieren soll das Programm wie folgt: Es wird ein Array von booleschen Werten angelegt, indiziert von 2 bis zur benötigten Größe, alle Einträge werden mit true initialisert. Der Wert false an Stelle i soll bedeuten, dass Zahl i sicher keine Primzahl ist. Wir durchlaufen die Zahlen ab i=2 bis zum Maximalwert und machen jeweils folgendes: Wenn der Eintrag an der Stelle i den Wert true hat, dann ist i eine Primzahl und diese wird ausgegeben, und alle Vielfachen von i werden in der Tabelle mit false gekennzeichnet. Implementiere dieses Verfahren, das als Sieb des Eratosthenes bekannt ist.

Mein Code sieht bisher so aus:

package main

import "fmt"
import "math"

func main() {
  var MAX_ZAHL int
  fmt.Println("Geben Sie die Zahl an, bis zu dessen Grenze die Primzahlen ausgegeben werden sollen!")
  fmt.Scanln(&MAX_ZAHL)
  fmt.Println("Die Primzahlen werden bis zu einer Größe von ", MAX_ZAHL, "ausgegeben")
}

Wie Arrays funktionieren, weiß ich. Aber durch die momentane Situation bei mir konnte ich nicht viel nachholen (und da mein Lehrer uns eher ohne Hilfen ausstattet).

Den boolschen Wert verstehe ich ebenfalls nicht so ganz.

Könnte mir jemand bei dieser Aufgabe helfen?

Danke im Voraus.

...zur Frage

Wie kann man die richtige Idee für ein Programm rekursiv lösen?

Mir fällt es aus irgendwelchen Gründen extrem schwer rekusiv zu denken und Programme für die Uni rekursiv zu schreiben. Mit schleifen usw. hab ich schnell eine Idee und auch wenn ich mir dann die rekursiven Musterlösungen anschaue frage ich mich oft, wie ich da nicht drauf kommen könnte. Könnt ihr dieses Problem nachvollziehen und habt ihr Tipps?

...zur Frage

Funktion für die Primfaktorzerlegung?

Diese Funktion soll die Primfaktoren einer Zahl berechnen und in der main funktion ausgeben. Tut sie auch. Das ist alles kein Problem. Ich verstehe nur nicht, was über dem Printf passiert. Was bedeutet das und warum wird das gemacht? Wenn ich das weg mache gibt mir der Debugger 2*2*2*2*2*2*2...........

Aber warum?

Ich hoffe, man kann mir helfen. Ich bin noch ein Neuling und versuche grade zu lernen. Danke

int primfakt(int zahl) { //Funktion für die Primfaktorzerlegung

int i = 2;

while (i <= zahl) // while schleife bis zur Zahl

{

if (zahl % i == 0) //Wenn zahl restlos Teilbar -> Ausgeben

{

zahl = zahl / i;

printf("%i*", i); //wird in der Main Funktion ausgegeben

}

else

i++; // ansonsten erhöhe i um 1

}

...zur Frage

Welches Programm nutzt mein Professor zum Ausführen von Programmen mit den Programmiersprachen Prolog und Haskell?

...zur Frage

Kann mir wer helfen?

hi,

ich habe eine Matheaufgabe, die ich nicht verstehe.

,,Denke dir eine Zahl. Multipliziere sie mit der um 2 verminderten Zahl. Addiere dazu das Vierfache der gedachten Zahl. Subtrahiere davon das Ergebnis der mit sich selbst multiplizierten gedachten Zahl. Nenne mir dein Ergebnis und ich sage dir deine gedachte Zahl.“

Führe die Zahlenzauberei mit verschieden Zahlen durch. Wie findet Herr Hutsch die gedachte Zahl? Begründe, indem du einen Term aufstellst.

Hiermit bin ich wirklich komplett überfordert. Vielleicht hat jemand Zeit mir zu helfen.

Mit freundlichen Grüßen

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen