Rekursive Funktion

[StareDog]

Hallo zsm,

haben uns in der letzten Vorlesung das erste Mal mit rekursiven Funktionen beschäftigt.

Schreiben Sie rekursive Funktionen zur Berechnung folgender Werte. Alle Intervalle sind inklusiv. Also
[a,b] = {a, a+1, ..., b}
Summe der Elemente eines Feldes a von Position p bis zum Ende des Feldes: summe(a,p)

Code: Alles auswählen

import random

def summe(a,p):
    a = [random.randint(0, 10) for i in range(0, 100)]

    if a[p:] == a[p]:
        return a[p]
    else:
        a[p]+a[p+1]
    return summe(a,p)

print(summe(100,40))

Ich bi nicht einmal sicher ob ich die Aufgabe richtig verstehe.

Ich denke ich soll irgendein Feld a generieren und dann von einer Stelle p innerhalb des Feldes a die Werte bis zum Schluss aufaddieren und dann ausgeben. Ist das korrekt?

Ich lasse hier in meinem Code deswegen ein Feld generieren und dort soll dann ein Punkt p bestimmt werden von dem ab alles aufaddiert wird bis das Feldende erreicht wird.


rekursion bedeutet, dass ich immer auf meine vorherigen werte zurückgreife, d.h. zuerst habe ich a[p] und dann addiere ich a[p+1] und dies bis das Feldende erreicht wird.

Ist in dem Code ansatzweise irgendwas richtig?

Über hinweise wie ich falsch denke oder wie ich an die sache herangehen muss, würde ich mich freuen.

Gruß StareDog

[ThomasL]

die Erzeugung deines Feldes a gehört nicht in die Funktion
denn so erzeugst du jedes mal wenn die Funktion aufgerufen wird, in der Funktion ein neues Feld a, das ist so definitiv nicht gewünscht

In der Definition der Funktion summe(a, p) sind a und p Platzhalter für Argumente die als Parameter beim Aufruf der Funktion übergeben werden
du möchtest diesen Argumenten in der Funktion nichts neues zuweisen (a = [random......)

der aufruf von summe(a, p) in der Funktion führt zur endlosen Rekursion ohne Abbruch

pseudo code für deine Funktion:

Code: Alles auswählen

feld = liste mit zahlen

funktion summe(a, b):
	if a < b:
		return feld[a] + summe(a+1, b)
	elif a == b:
		return feld[a]
	else:
		raise "Fehler: Index a muss kleiner gleich Index b sein"

[ThomasL]

wenn du zumindest Englisch verstehen kannst, ist dieses Video hier interessant für dich

https://www.youtube.com/watch?v=Mv9NEXX1VHc

[kbr]

@StareDog: Eine Funktion nennt man rekursiv, wenn diese sich im Verlauf ihrer Ausführung selbst aufruft. Damit dies nicht unendlich oft geschieht, muß es eine Abbruchbedingung geben.

In Deinem konkreten Fall hast Du eine Sequenz (Feld ist in Python eine eher unglückliche Bezeichnung) und sollst eine Funktion erstellen, die ab einer bestimmten Position in der Sequenz die Summe aller Elemente bis zum Ende der Sequenz ermittelt.

Dies könnte eine Funktion sein, die eine Sequenz 'a', eine Startposition 'p', sowie die bisherige Summe 's' (per default gleich Null) als Parameter erhält. Dann brauchst Du zu 's' lediglich a von p addieren und das Ergebnis des erneuten Aufrufs der Funktion (mit den nun passenden Parametern) zurück geben. Nun kann es aber sein, dass p kein gültiger Index von a ist. Den Fall musst Du abfangen und dann – ja, was? – zurück geben.

Wenn Du das verstanden hast, dann hast Du Rekursion verstanden und auch Deine Aufgabe gelöst.

[StareDog]

nur mal so als beispiel
ich hab jetzt eine sequenz
a = [3,6,8,9,6,4,10,16,18,22,7,2]

jetzt habe ich p = 5, das wäre dann
a[5] = 4

ab dieser position werden dann die werte aufaddiert, also
4+10+16+18+22+7+2
also
s = a[p] + a[p+1]
p+=1
und dann wird abgebrochen, weil die Summe von p bis zum ende der sequenz aufaddiert wurden. ist das richtig?

terminiert wird, wenn das ende von a, also hier b erreicht wird.

was hat es eigentlich mit diesem intervall (a, a+1,... b) auf sich? a ist doch ein feld und nicht das erste glied eines intervalls?

glaub ich brauch noch etwas bis ich das kapiere...

das video ist gut, aber für mein beispiel hier kam ich damit trotzdem nicht weiter

trotzdem danke

[ThomasL]

du hattest geschrieben:

Schreiben Sie rekursive Funktionen zur Berechnung folgender Werte. Alle Intervalle sind inklusiv. Also
[a,b] = {a, a+1, ..., b}
Summe der Elemente eines Feldes a von Position p bis zum Ende des Feldes: summe(a,p)

ich vermute, dass mit [a,b] = {a, a+1, ..., b} explizit die Aussage "Alle Intervalle sind inklusiv" definiert werden soll,
d.h. das Feld (oder die Liste) [10, 13] enthält die Elemente [10, 11, 12, 13], also auch den Wert b

Die Bezeichnung a für ein Feld (oder Liste) im nächsten Satz ist schon verwirrend, steht das wirklich so in der Aufgabe?

Ich verstehe die Aufgabe jetzt so, dass der Funktion summe(a, p) als ersten Parameter a ein Feld (oder Liste) und mit Parameter p die Position (oder Zeiger/Index) übergeben wird.
Die Funktion soll dann alle Werte im Feld (oder Liste) a angefangen an Position p bis zum Ende aufsummieren.

Das kann man rekursiv dann so formulieren:

Code: Alles auswählen

def summe(a, p):
	if   # Bedingung  p ist kleiner dem Index des letzten Elementes von a
		return a[p] + summe(a, p+1)
	elif # Bedingung  p ist gleich dem Index des letzten Elementes von a
		return a[p]
	else:
		# Fehler  p ist grösser dem Index des letzten Elementes von a

Die Abbruchbedingung für die Rekursion ist, wenn p gleich dem Index des letzten Elementes von a ist.
Dann wird der Wert dieses Elementes und danach Schritt für Schritt die Summe an die jeweils aufrufende Ebene zurück gegeben.

[StareDog]

verstehe ich das richtig? a(p) ist dann der wert an der stelle a(b) also dem letzten element von a. und von dort aus wird dann alles aufsummiert bis wir in der mitte angekommen sind. das ist dann die rekursive vorgehensweise.

iterativ würde man doch alle werte einfach von dem wert beginnend bis zum ende einfach aufaddieren a la

Code: Alles auswählen

s=0
for i in range (p,b+1):
      s = s + a[i]

und rekursiv

Code: Alles auswählen

def summe(a, p):
	if   # Bedingung  p ist kleiner dem Index des letzten Elementes von a
		return a[p] + summe(a, p+1)
	elif # Bedingung  p ist gleich dem Index des letzten Elementes von a
		return a[p]
	else:
		# Fehler p ist grösser dem Index des letzten Elementes von a

ich versteh nicht wieso return a[p] beim letzten index ausgegeben wird. egtl. ist das doch dann a == a[p+ len(p,b+1).

was macht der code geenau? er hat ein gegebens a[p] und zu diesem wird hinzuaddiert die summe (a,p+1), welche wir nicht kennen? richtig? eigentlich ergibt doch die summe (a,p) die summe von a[p] + summe[a,p-1) also die summe der vorhergenden werte. komm hier ganz durcheinander....

[StareDog]

Die Bezeichnung a für ein Feld (oder Liste) im nächsten Satz ist schon verwirrend, steht das wirklich so in der Aufgabe?

ja stand genau so in der aufgabe

[Sirius3]

Das ist das Problem mit so künstlichen Rekursionsaufgaben, weil die iterative Lösung so offensichtlich ist, und es keinen Sinn macht, eine andere, kompliziertere Lösung, zu suchen.

Bei Rekursionsproblemen weiß man zwar nicht die Lösung, wenn man aber die Lösung zu einem ganz ähnlichen Problem kennen würde, dann ist das ursprüngliche Problem auch gelöst. Hier also: ich weiß nicht wie ich die Zahlen p bis Ende aufaddieren kann, wenn ich aber wüßte, was das Ergebnis der Summe p+1 bis Ende ist, ist das Gesamtergebnis a[p] + summe von a[p+1 bis Ende].
Jetzt muß man nur noch einen Schluß der Rekursion finden, wo das Ergebnis auch bekannt ist, also, z.B. wenn p größer ist als die Anzahl der Elemente in der Liste, ist das Ergebnis 0.

[ThomasL]

Beispiel:

Code: Alles auswählen

feld = [1,2,3,4,5,6]  # also [a, b] mit a=1 und b=6 gemäß der Definition in der Aufgabenstellung

def summe(a, p):
    # a ist unsere Liste 'feld' und p ist der Index ab dem summiert werden soll
    if p < len(a)-1:
    	# len(a) gibt in diesem Beispiel 6 zurück, das letzte Element hat aber den Index 5, deshalb -1
    	# wenn p kleiner als 5 ist nehmen wir den Wert an der aktuellen Stelle p und addieren den Summenwert der Elemente ab Stelle p+1 bis zum Ende der Liste
    	return a[p] + summe(a, p+1)
    else:
    	# wenn p gleich 5 ist, sind wir am Ende der Liste und geben nur den Wert von a[p] zurück, das ist dann das Ende der Recursion
    	return a[p]
    # die 3. Möglichkeit ignorieren wir mal

print(summe(feld, 3))
# Es sollte 15 ausgegeben werden

wir starten mit Index 3
summe(feld, 3) # 1. Aufruf von Summe()
3 ist kleiner als 5
return a[3] + summe(a, 4) # 2. Aufruf von Summe()
4 ist kleiner als 5
return a[4] + summe(a, 5) # 3. Aufruf von Summe()
5 ist gleich 5
return a[5]

die Rekursion ist beendet und nun geht es rückwärts
der 3. Aufruf von Summe() gibt a[5] also 6 zurück
im 2. Aufruf wird jetzt die Summe von a[4] + 6 also 5+6=11 zurück gegeben
im 1. Aufruf wird jetzt die Summe von a[3] + 11 also 4+11=15 zurück gegeben
print() gibt 15 aus

[kbr]

Also, wenn hier schon Hausaufgaben gelöst werden, dann finde ich ja

Code: Alles auswählen

def summe(a, p, s=0):
    try:
        s += a[p]
    except IndexError:
        return s
    return summe(a, p+1, s)

schöner. Wobei ich der Ansicht bin, dass es (zumeist) dem Lerneffekt abträglich ist, derlei hier zu präsentieren. Die Funktion gibt allerdings auch dann 0 zurück, wenn p bereits zu Beginn ungültig ist. Ist mir aber egal, denn am besten wäre:

Code: Alles auswählen

sum(a[p:])

[Sirius3]

@kbr: das ist ja nicht wirklich eine sinnvolle Rekursion. Du übergibst das Teilergebnis immer an die nächste Funktion weiter und zum Schluß wird nur das Endergbnis über die gesamte Verschachtelungskette zurückgegeben.

Also wenn schon Hausaufgaben, dann wenigstens Musterlösungen:

Code: Alles auswählen

def summe(a, p=0):
    try:
        return a[p] + summe(a, p + 1)
    except IndexError:
        return 0

[ThomasL]

@kbr
@Sirius3

Eure Beiträge mögen Python Code a-la-carte sein haben aber Lerneffekt = 0
da ich bezweifle, dass diese geistigen Ergüsse dem Threadstarter bei seinem Verständnisproblem helfen

[StareDog]

hey, dankeschön für eure Mühen, insbesondere Thomas.

also ich glaub ich habs jetzt etwas besser verstanden. Ist wohl wie Sirius meint auch blöd, dass eigentlich in dem fall die iterative Lösung viel offensichtlicher ist und das andere mir dann komisch vorkommt.

Die Darstellung summe (a,p) bedeutet also. Summe im Feld a von p bis Ende oder? bzw. je nach formel auch anders? theoretisch könnte ich ja auch summe von p bis anfang des feldes machen. da müsste ich dann mit p-1 bis Abbruchbedingung p = 0 oder?

Code: Alles auswählen

import random

a = [random.randint(0,10) for i in range(0,100)]
def summe(a,p):
    if p>0:
        return a[p]+summe(a,p-1)
    else:
        return a[p]

print(summe(a,22))

[StareDog]

ok, habs jetzt mit nem Feld gemacht wo ich es dann auch nachvollziehen kann

Code: Alles auswählen

a = [1,2,3,4,5,6,7,8,9,10,11]
def summe(a,p):
    if p>0:
        return a[p]+summe(a,p-1)
    else:
        return a[p]

print(summe(a,4))

Denke habs jetzt zumindest an diesem Beispiel verstanden. Dankeschön

[Sirius3]

Ich würde für die Endbedingung noch um ein Element weiter gehen:

Code: Alles auswählen

def summe(a, p):
    if p<0:
        return 0
    return a[p] + summe(a, p-1)

[StareDog]

Also du meinst für die Fälle, indem p negativ ist, ist bei mir keine Lösung gegeben und deswegen ist deine Endbedingung besser? bzw. für negative p wird auch a[p] zurückgegeben. Stimmt, danke.

Code: Alles auswählen

a = [1,2,3,4,5,6,7,8,9,10,11]
def summe(a,p):
    if p>0:
        return a[p]+summe(a,p-1)
    if p=0
        return a[p]
    else:
        return (0)

print(summe(a,4))

also so!

[Sirius3]

Jetzt ist nur noch der Fall `p=0` falsch geschrieben (==) und überflüssig, weil er schon durch den ersten if-Block abgedeckt wird. Und die Klammern um die 0 gehören weg.

[ThomasL]

Also du meinst für die Fälle, indem p negativ ist, ist bei mir keine Lösung gegeben und deswegen ist deine Endbedingung besser? bzw. für negative p wird auch a[p] zurückgegeben. Stimmt, danke.

Code: Alles auswählen

a = [1,2,3,4,5,6,7,8,9,10,11]
def summe(a,p):
    if p>0:
        return a[p]+summe(a,p-1)
    if p=0
        return a[p]
    else:
        return (0)

print(summe(a,4))

in deinem ersten Post stand als Aufgabe
"Summe der Elemente eines Feldes a von Position p bis zum Ende des Feldes "
mit obigen Code ist diese Aufgabe nicht erfüllt

[Sirius3]

@ThomasL: jetzt willst Du also ernsthaft kritisieren, dass der OP das gelernte an einer modifizierten Aufgabe verifiziert?