Haskell-Forum
Gepostet: |
Rekursion an einem Beispiel | ||||||||||
| Hallo habe eine frage zu rekursiven funktionsaufrufen. Beispiel: liste = [0,1,2,3,4,5,6] p [] = 3000 p [e] = e p (a:b:r) = p r + a+b + p r test = (p liste) wenn ich einen aufruf von test durchspiele: p aufgerufen mit [0,1,2,3,4,5,6] ==> dritte funktion wird aufgerufen ==> a=0, b=1, r=[2,3,4,5,6] ==> p wird mit r aufegrufen ==> dritte funktion wird aufgerufen ==> a=2,b=3,r=[4,5,6] ==> p wird mit r aufgerufen ==> entspricht noch immer der dritten funktion ==> a=4,b=5,r=[6] ==> p wird mit r aufgerufen ==> entspricht jetzt der zweiten funktion ==> 6 wird zurückgegeben. das heißt nun das die erste rekursion auffolge, nämlcih der aufruf von p r fertig ist und den wert 6 ergibt. nun gehts weiter zu a+b. jetzt muss ich der rekursion entlang die werte von a und b addieren. (4+5) + (2+4) + (0+1) = 16 also hätten wir jetzt bis hier her p r + a+b den wert 22. die dritte funktion geht aber noch weiter nämlich wird nochmal + p r dazu addiert . p r ergibt ja 6. dh. 22 + 6 = 28. Leider müsste hier aber 95 rauskommen und nicht 28. Wo ist mein denkfehler? lg |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Das Problem ist, (p r) wird in jeder Rekursion zweimal aufgerufen, dazu noch a+b. Davon hast du einige vergessen. test = p [0,1,2,3,4,5,6] = (p [2,3,4,5,6]) + 0+1 + (p [2,3,4,5,6]) = (p [4,5,6] + 2+3 + p [4,5,6]) + 0+1 + (...) = ( (p [6] + 4+5 + p [6]) + 2+3 + (p [6] + 4+5 + p [6]) ) + 0+1 + (...) = ( (6+4+5+6) + 2+3 + (6+4+5+6) ) + 0+1 + (...) = (21+5+21) + 0+1 + (...) = 47 + 1 + (47) -- die 47 hinten ist das gleiche wie vorn = 95 Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| = p [0,1,2,3,4,5,6] = (p [2,3,4,5,6]) + 0+1 + (p [2,3,4,5,6]) = (p [4,5,6] + 2+3 + p [4,5,6]) + 0+1 + (...) = ( (p [6] + 4+5 + p [6]) + 2+3 + (p [6] + 4+5 + p [6]) ) + 0+1 + (...) = ( (6+4+5+6) + 2+3 + (6+4+5+6) ) + 0+1 + (...) = (21+5+21) + 0+1 + (...) = 47 + 1 + (47) -- die 47 hinten ist das gleiche wie vorn = 95 also in der zweiten zeile ist p l + a+b + p l angegeben und ab der dritten zeile entsprechen die (...) dem zweiten rekursionsaufruf in der zeile und müssten eigentlich gleich ausschauen wie das was vor dem (...) alles steht. das hoff ich zumindes mal :-D |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Nicht ganz alles was vor dem (...) steht, aber alles was zum rekursiven Aufruf von (p l) gehört. Das a+b taucht ja nur einmal auf, also das ist dann hinten nicht nochmal dabei. | |||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| ok... nun, da ich es mir ausführlich auf einem zettel aufgeschrieben habe komme ich aufs ergebnis 95 :) Aber so ausm Kopf heraus ist das schon etwas.... naja... wenn man nicht täglich mit rekursion zu tun hat.... danke für die hilfe |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Bei diesem beispiel würd ich folgendermaßen vorgehen: mnr = [0,5,1,6,4,3,3] p [] = 5000 p [e] = e p (a:b:l) | a <= b = p (b:l) p (a:l) = p l + a + p l t7 = ( p mnr) -------------------- p[0,5,1,6,4,3,3] =p[5,1,6,4,3,3] =p[1,6,4,3,3] + 5 + p[1,6,4,3,3] =p[6,4,3,3] + 5 + p[6,4,3,3] =p[4,3,3] + 6 + p[4,3,3] + 5 + (...) =p[3,3] + 4 + p[3,3] + 6 + p[3,3] + 4 + p[3,3] + 5 + (...) =(p[3] + 3 + p[3]) + 4 + (p[3] + 3 + p[3]) + 6 + (p[3] + 3 + p[3]) + 4 + (p[3] + 3 + p[3]) + 5 + (...) = 97 laut interpreter sollte hier aber 57 rauskommen. siehst du wo ich mich verirre? |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| (p [3,3]) löst du zu (p [3] + 3 + p [3]) auf, es sollte aber zu (p [3]) und dann zu 3 abgeleitet werden, denn im Guard von p steht "a kleiner gleich b". | |||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Okay nun komme ich auch auf 57. Mein Fehler war dass ich mir nicht gedacht habe dass ein aufruf mit p[3,3] auf das muster p (a:b:l) matcht. habe p[3,3] gleich auf das muster p(a:l) angewendet. Er matcht aber trotzdem weil [3,3] nichts anderes ist wie e und drei und leere (rest)liste richtig? danke für den hinweis. |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| > Er matcht aber trotzdem weil [3,3] nichts anderes ist wie e und drei und leere (rest)liste richtig? Na das e ist aber aus nem anderen Fall, aber sonst stimmt's schon, [3,3] ist das gleiche wie 3:3:[]. |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| > Na das e ist aber aus nem anderen Fall, aber sonst stimmt's schon, [3,3] ist das gleiche wie 3:3:[]. hehe ja hab mich nur verschrieben ;) thx |
|||||||||||
| Zum Seitenanfang | |||||||||||
