Informatiker Board | Praktische Informatik

Informatiker Board » Themengebiete » Praktische Informatik » Hilfe Rekursion (Haskell)

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Hilfe Rekursion (Haskell)

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

Hilfe Rekursion (Haskell)

Zitatantwort auf diesen Beitrag erstellen

Funktion1 1 = 10 (wenn für n die Zahl 1 eingegeben wird, dann gib 10 zurück).
Funktion1 n = if even (n-1) then ((3*Funktion1 (n-1))-17) ‘div‘ 2

else 3*(Funktion1 (n-1))-17

laut skript erhält man für die eingabe von n=2 die 13 und für n=3 die 11 (als jeweiliges endergebnis.)

ich verstehe nicht wie diese zwei Zahlen zustande kommen. Bei der else Zeile wie wird denn da gerechnet? also sei n=2

3*(n-1)-17
=3*(2-1) - 17
=3* (1) - 17
=3-17
= -14

wie kommt man also bitte auf die 13?

Mir ist klar das bei der Rekursion die Funktion mehrmals selber aufgerufen wird. Aber das endgerebnis kann ich nicht nachvollziehen. Bitte helft mir.

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von nature6: 16.04.2020 17:16.

16.04.2020 17:08

Nehmen Sie nature6 in Ihre Freundesliste auf

NixJava
unregistriert

Zitat:

3*(n-1)-17
=3*(2-1) - 17
=3* (1) - 17
=3-17
= -14

Du hast den Funktionsaufruf unterschlagen:
3 * Funktion1(n-1) - 17
3 * Funktion1(1) - 17 = 3 * 10 - 17 = 13

Für n=3 kannst du den Wert von Funktion1(2) verwenden und "((3 * Funktion1(2)) - 17) div 2" auswerten.

16.04.2020 17:32

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

Danke. Wenn ich allerdings in den Taschrechner für n=3 eingebe, erhalte ich

(3*(3-1)-17) / 2
=-5,5

verwirrt

Edit: okay. ich habe jetzt die 11 erhalten nachdem ich den wert der funktion1(2) in der ersten zeile in if eingegeben und ausgerechnet habe. Anschließend habe ich das ergebnis auch mit n=4 im unteren else zweig getestet. mit funktion1(3).

aber wieso muss ich denn so rechnen? wieso kann ich das nicht einfach so im taschenrechner wie oben für n=3 eingeben?

Am anfang hatte ich nämlich gedacht das "Funktion1 1 = 10" eigentlich die Bedingung war wenn das Programm "beenden" soll. sprich: wenn das programm von n-1, also z.B 5-1 bis nach unten zu 2-1 rechnet.

Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von nature6: 16.04.2020 18:29.

16.04.2020 17:49

NixJava
unregistriert

Zitat:

Wenn ich allerdings in den Taschrechner für n=3 eingebe, erhalte ich

(3*(3-1)-17) / 2
=-5,5

Das ist nochmal der gleiche Fehler.
Du darfst nicht einfach (3-1) einsetzen, sondern Funktion1(3-1). Und diesen Wert haben wir schon berechnet, er beträgt 13.

Zitat:

Edit: okay. ich habe jetzt die 11 erhalten nachdem ich den wert der funktion1(2) in der ersten zeile in if eingegeben und ausgerechnet habe

Genau!

Zitat:

aber wieso muss ich denn so rechnen? wieso kann ich das nicht einfach so im taschenrechner wie oben für n=3 eingeben?

Weil die rekursive Funktion so definiert wurde. Augenzwinkern

Zitat:

Am anfang hatte ich nämlich gedacht das "Funktion1 1 = 10" eigentlich die Bedingung war wenn das Programm "beenden" soll.

Nun ja, "Funktion1 1 = 10" ist die Abbruchbedingung. Bei dieser Rekursion ruft sich die Funktion selbst wieder auf, allerdings mit einem anderen Parameter (sonst würde man in einer Endlosschleife landen). Die natürliche Zahl n wird in jedem Durchlauf um 1 dekrementiert. Damit auch dieser Aufrufprozess endet, ist eine Abbruchbedingung nötig.

16.04.2020 22:28

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

danke nochmals. Wink

ich habe das mal auf andere rekursionsbeispiele übertragen und konnte die denke ich nachvollziehen. Jetzt bin ich leider wieder an einem punkt im skript angekommen wo ich am schlauch stehe. Ich hoffe das ist kein Problem wenn es sich hierbei um listen in haskell handelt.

also im skript steht folgendes was mich verwirrt. erstmal hier der Quellcode

letztesElement :: [a] -> a
letztesElement xs = if null xs then
error "Liste ist leer"
else if null (tail xs) then head xs
else letztesElement (tail xs)

aus dem skript:
Die in Haskell vordefinierte Funktion null :: [a] -> Bool testet, ob eine Liste leer ist. Mit head, tail und null kann man beispielsweise eine Funktion definieren, die das letzte Element einer Liste extrahiert:

Für eine Liste mit mehr als einem Element ruft sich letztes Element rekursiv mit dem Schwanz der Liste auf. Enthalt die Liste nur ein Element (der Test hierfür ist null (tail xs)), so wird das erste Element dieser Liste als Ergebnis zurück geliefert (dies ist der Rekursionsanfang). Der Fehlerfall, dass die Liste gar keine Elemente enthält, wird direkt am Anfang abgefangen, und eine Fehlermeldung wird generiert. Der Typ der FunktionletztesElement ist[a] -> a, da sie eine Liste erhält (hierbei ist der konkrete Typ der Elemente egal) und ein Listenelement liefert.

im skript steht das in der zweiten if abfrage mittels der funktion "null" geprüft wird ob die liste leer ist. Wenn also null = true ist, also der hintere teil (tail xs) der liste leer ist, wird das erste element dieser liste als ergebnis zurückgeliefert.

das verstehe ich nicht. wenn im hinteren abschnitt einer liste keine elemente vorhanden sind, wie kann dann eine liste ein element ganz vorne haben? Wird eine Liste denn nicht für gewöhnlich von rechts nach links aufgefüllt?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von nature6: 17.04.2020 02:32.

17.04.2020 02:31

NixJava
unregistriert

Zitat:

wenn im hinteren abschnitt einer liste keine elemente vorhanden sind, wie kann dann eine liste ein element ganz vorne haben?

Sei eine Liste [1,2,3,4] gegeben. Dann ist

code:
1:	head[1,2,3,4] = 1

und

code:
1:	tail[1,2,3,4] = [2,3,4]

Jetzt wird die Funktion "letztesElement" jeweils rekursiv mit dem Parameter "tail[Liste]" aufgerufen, also

code:

1:
2:
3:
4:
5:

letztesElement([1,2,3,4])
  letztesElement(tail[1,2,3,4]) = letztesElement([2,3,4])
    letztesElement(tail[2,3,4]) = letztesElement([3,4])
      letztesElement(tail[3,4]) = letztesElement([4])
        letztesElement(tail[4])

Im letzten Aufruf ist tail([4]) = null, also wird head[(4)] = 4 zurückgegeben und dies ist - wie gewünscht - das letzte Element der Liste.

17.04.2020 14:02

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

Hallo nixJava, Danke nochmals. smile

die (tail[4]) ist aber indem fall nicht das "x" von (x:xs) oder?
ich hatte angenommen das das erste element einer liste immer "x" ist?

meine frage bezieht sich jetzt auf die folgende aussage:

Enthalt die Liste nur ein Element (der Test hierfür ist null (tail xs)), so wird das erste Element dieser Liste als Ergebnis zurück geliefert (dies ist der Rekursionsanfang).

Ich hoffe dich stört es nicht wenn ich noch weitere fragen zum skript stelle:

eigenesHead [] = error "empty list"
eigenesHead (x:xs) = x

Die Definition von eigenes Head ist hierbei so zu interpretieren: Wenn die Eingabe eine Liste ist, die zu dem Muster (x:xs) passt (die Liste daher mindestens ein Element hat), dann gebe den zu x passenden Teil zurück und wenn die Liste zum Muster [] passt (die Liste daher leer ist) dann generiere eine Fehlermeldung. Die Fälle werden bei der Auswertung von oben nach unten geprüft. Analog ist tail definiert als.

hier eigentlich nochmal diesselbe frage. Wenn ein Element in der Liste ist. Ist doch also lediglich x gegeben? Dann passt das Muster (x:xs) doch eigentlich nicht, oder? verwirrt

eigenesTail [] = error "empty list"
eigenesTail (x:xs) = xs

Eine mögliche Definition für null ist die Funktion:

eigenesNull [] = True
eigenesNull (x:xs) = False

Da die Muster von oben nach unten abgearbeitet werden, kann man alternativ auch definieren:

eigenesNull2 [] = True
eigenesNull2 xs = False

Wieso kann man hier lediglich xs benutzen? x kann ja immer noch mit einem element versehen sein? Würde doch heißen das die liste nicht leer ist?

In diesem Fall passt das zweite Muster (es besteht nur aus der Variablen xs) für jede Liste.Trotzdem wird für den Fall der leeren Liste True zurückgeliefert, da die Muster von oben nachunten geprüft werden. Falsch wird die Definition, wenn man die beiden Fälle in falscher Reihenfolge definiert:

falschesNull xs = False
falschesNull [] = True

und worin liegt hier bitte der unterschied? wieso ist die defintion in diesem fall falsch? unglücklich

Da das erste Muster immer passt, wird die Funktion falschesNull für jede Liste False liefern. Der GHC iist so schlau, dies zu bemerken und liefert beim Laden der Datei eine Warnung

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von nature6: 18.04.2020 17:52.

18.04.2020 17:48

NixJava
unregistriert

Vorab: Ich habe wenig Ahnung von Haskell und muss mir die Sachen teilweise selbst zusammenreimen. Meine Antworten sind daher als Ideen aufzufassen und sollten zusätzlich nochmal selbst durchdacht und überprüft werden.

Zitat:

die (tail[4]) ist aber indem fall nicht das "x" von (x:xs) oder?

Die Liste [4] lässt sich als 4 : [] (vgl. x:xs) ausdrücken, also head[4] = 4 und tail[4] = null.

Zitat:

ich hatte angenommen das das erste element einer liste immer "x" ist?

Ja, wenn man die Liste in der Form (x:xs) auffasst.

Zitat:

Wenn ein Element in der Liste ist. Ist doch also lediglich x gegeben? Dann passt das Muster (x:xs) doch eigentlich nicht, oder?

Doch, weil man die Liste [a] mit einem Element a als a : [] notieren kann.

Zitat:

Wieso kann man hier lediglich xs benutzen? x kann ja immer noch mit einem element versehen sein? Würde doch heißen das die liste nicht leer ist?

xs ist in diesem Fall einfach eine Variable. Ein Muster, das auf jede Liste zutrifft. xs hat in diesem konkreten Fall nichts mit dem Listenschwanz (x:xs) zu tun.

Zitat:

und worin liegt hier bitte der unterschied? wieso ist die defintion in diesem fall falsch?

"falschesNull xs = False" würde auch bei einer leeren Liste "False" liefern. Weil die Muster der Reihe nach bearbeitet werden, muss man zunächst "falschesNull [] = True" abfragen.

19.04.2020 12:47

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

vielen Dank nochmal. Ich fange es an besser zu verstehen
Deine Erklärungsversuche scheinen mir jedenfalls logisch. Ich hoffe du bist auch weiterhin über dem Board hier erreichbar. Es ist wirklich schön wenn einem hier geholfen wird. smile

magst du mir bitte noch diese gleichung erklären, die ich als sceenshot hochgeladen habe?
Leider sind auch meine Mathekenntnisse nicht die Besten. Ich verstehe leider nicht die darstellung der index sowie exponentenreihe.

also:

z_n +z_n-1 ... + z_1 + z_0 + z_-1 ... + z_-m

wenn ich beispielsweise für n die Zahl 5 einsetzte dann wird der index n (um auf die -1 zu kommen) n-6 sein?

z_5 + z_5-1 + z_5-2 + z_5-3 + z_5-4 + z_5-5 + z_5-6

ist diese überlegung richtig? wieso wird dann am ende der Reihe ein z_-m angegeben? verwirrt

tut mir leid wenn für euch das zu banal erscheint.

nature6 hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von nature6: 22.04.2020 04:40.

22.04.2020 04:39

NixJava
unregistriert

Zitat:

z_5 + z_5-1 + z_5-2 + z_5-3 + z_5-4 + z_5-5 + z_5-6

Du musst mit der Notation aufpassen und Klammern setzen. Deine Schreibweise bedeutet
[latex]z_5 + z_5-1 + z_5-2 + z_5-3 + z_5-4 + z_5-5 + z_5-6[/latex]

.

Gemeint ist aber
$[latex]z_5 + z_{5-1} + z_{5-2} + z_{5-3} + z_{5-4} + z_{5-5} + z_{5-6}[/latex]$ .

(In der Summe auf dem Screenshot sind noch b's vorhanden, die du hier nicht erwähnt hast.)

Zitat:

wieso wird dann am ende der Reihe ein z_-m angegeben?

Die Summe muss nicht mit dem Index "-1" enden. m ist die untere und n die obere Grenze. Es sind zwei Zahlen anzugeben. Für [latex]n=3[/latex]

und

also

$[latex]\sum_{i=-2}^3 z_ib^i = z_{-2}b^{-2} + z_{-1}b^{-1} + z_0b^0 + z_1b^1 + z_2b^2 + z_3b^3[/latex]$

oder in umgekehrter Reihenfolge aufgeschrieben, wie auf dem Bild. Es sollte noch erwähnt werden, was bei [latex]m > n[/latex]

passiert. In diesem Fall entsteht die leere Summe, die als 0 definiert ist, also bspw.

$[latex]\sum_{i=2}^{-1} z_ib^i = 0[/latex]$

22.04.2020 12:03

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

Zitat:

Die Summe muss nicht mit dem Index "-1" enden. m ist die untere und n die obere Grenze. Es sind zwei Zahlen anzugeben. Für [latex]n=3[/latex]

und

also

$[latex]\sum_{i=-2}^3 z_ib^i = z_{-2}b^{-2} + z_{-1}b^{-1} + z_0b^0 + z_1b^1 + z_2b^2 + z_3b^3[/latex]$

oder in umgekehrter Reihenfolge aufgeschrieben, wie auf dem Bild.

Hallo nixjava. Wieso hast du bitte ab i=0 nicht mehr die -2 beibehalten? ich glaube jetzt habe ich denn Faden völlig verloren. wenn man also nun für m=-2 einsetzt, dann würde es doch wie folgt aussehen?

$[latex]\sum_{i=-2}^3 z_ib^i = z_{-(-2)}b^{-2} + z_{-1(-2)}b^{-1} + z_{0-2}b^0 + z_1b^1 + z_2b^2 + z_3b^3[/latex]$

hab es ab 0 nicht mehr weiter ausgeführt. Wie kommst du bitte jetzt auf die -2, -1, 0, 1 usw.. im Index bzw. im Exponenten im Bezug auf n bzw. m? unglücklich

22.04.2020 13:39

NixJava
unregistriert

Ups, da ist mir ein Fehler unterlaufen: Bei $[latex]\sum_{i=-m}^n[/latex]$ sollte es [latex]m=2[/latex]

heißen (habe das Minus bei i=-m nicht beachtet). Dann startet der Index [latex]i[/latex]

bei -2. Mit [latex]m=-2[/latex]

würde er bei 2 starten.

Zitat:

wenn man also nun für m=-2 einsetzt, dann würde es doch wie folgt aussehen?
$[latex]\sum_{i=2}^3%20z_ib^i =z_{-(-2)}b^{-2} +z_{-1(-2)}b^{-1} +z_{0-2}b^0 +z_1b^1 + z_2b^2 + z_3b^3[/latex]$

Bei

sieht es so aus: $[latex]\sum_{i=2}^3 z_ib^i = z_2b^2 + z_3b^3[/latex]$ .

Mit [latex]n=3, m=2[/latex]

ergibt sich $[latex]\sum_{i=-2}^3 z_ib^i = z_{-2}b^{-2} + z_{-1}b^{-1} + z_0b^0 + z_1b^1 + z_2b^2 + z_3b^3[/latex]$ .

Sorry für die Verwirrung. Ich hoffe, es ist jetzt klarer.

22.04.2020 14:27

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

Leider verstehe ich jetzt gar nichts mehr.

mit welcher "ober bzw. untergrenze" arbeiten wir hier. Etwa ausschließlich mit [latex]n-1[/latex]

oder

?
bei der dekrementierung von

$[latex] z_{3} + z_ {3-1} + z_{2-1} + z_{1-1} = z_{3} + z_ {2} + z_{1} + z_{0} [/latex]$

verstehe ich das. Aber wie läuft denn die dekrementierung von -m ab? sei m=2. also -2.
muss man etwa nun -m+1 daraus machen, damit es auffaddiert?

also

$[latex] z_{-2} + z_ {-2+1} + z_{-1+1} = z_{-2} + z_ {-1} + z_{0} [/latex]$

verwirrt

ich habe

mal absichtlich außen vor gelassen.

Dieser Beitrag wurde 7 mal editiert, zum letzten Mal von nature6: 22.04.2020 20:55.

22.04.2020 20:52

as_string as_string ist männlich

Haudegen

Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg

Du denkst da viel zu kompliziert.
Du summierst alle [latex]z_i[/latex]

auf. und i läuft von -m bis +n.
In der Aufgabe ist es nur umgekehrt geschrieben, startend mit dem größten i. Das größte i ist +n. Das zweit größte (also eins kleiner) ist dann n-1. Das nächste i, also noch ein kleiner, ist dann n-2 und so weiter.
Angenommen n ist 3 und m ist 2, dann sind Deine i der Reihe nach:
+3, +2, +1, 0, -1, -2
Sie laufen also von n bis -m und Du musst dann rechnen:
$[latex]\sum_{i=-m}^{+n} z_i = z_3 + z_2 + z_1 + z_0 + z_{-1} + z_{-2}[/latex]$
Oder Du lässt das i von -m bis +n laufen, aber bei einer Summe ist ja die Reihenfolge egal, deshalb ist es äquivalent:
$[latex]z_3 + z_2 + z_1 + z_0 + z_{-1} + z_{-2} = z_{-2} + z_{-1} + z_0 + z_1 + z_2 + z_3[/latex]$

Gruß
Marco

27.04.2020 16:09

Nehmen Sie as_string in Ihre Freundesliste auf

nature6
Jungspund

Dabei seit: 16.04.2020
Beiträge: 11

vielen dank, as_String smile

28.04.2020 16:03

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Hilfe Rekursion (Haskell)