Rekursive Funktion - was soll sie bewirken?

[Andre24HGW]

Hallo alle Zusammen,

ich bin Neuling. Nun habe ich eine Aufgabe bekommen, eine rekursive Funktion als nicht-rekursive Funktion (mit Schleifen) zu schreiben. Natürlich soll das Ergebnis gleich sein.

Ich habe lange daran gesessen und es letztlich hinbekommen. Mehrere Tests bestätigen die Funktionalität. Eigentlich könnte ich froh sein. Nein, ich bin ja sogar begeistert.

Leider ist eine Teilaufgabe davon, herauszufinden was diese Funktion bewirkt. Leider finde ich nichts im Netz. Kann mir einer einen kleinen Tipp geben, wo ich geziehlt suchen kann, bzw. wie evtl. die Funktion heißt? Besten Dank im Voraus für Eure Unterstützung!

Gegebene Rekursion:

Code: Alles auswählen

def mache_etwas(n):
  '''Funkton zur ??? aus dem
     übergebenen Startwert n'''
  if n == 0:
    return 4
  else:
    return 4/(2*n+1) + (-1**n) * mache_etwas(n-1)

Meine nicht-Rekusion

Code: Alles auswählen

# Deklaration der Variablen mit Startwert 
start_wert = int(input('Geben Sie den Startwert an: '))
ergebnis_1 = 0
ergebnis_2 = 0
# Bedingung falls Startwert = 0
if start_wert == 0:
  ergebnis_1 = 4
else:
# Beginn Schleifendurchlauf von 1 bis start_wert
  for i in range(start_wert+1):
    ergebnis_2 = 4/(2*i+1)+(-1**(i+1))*ergebnis_1
    ergebnis_1 = ergebnis_2
# Ausgabe auf Bildschirm
print('Ergebnis durch Rekursion:  ',mache_etwas(start_wert))
print('Ergebnis durch Schleife:   ',ergebnis_2)

[nezzcarth]

Kann mir einer einen kleinen Tipp geben, wo ich geziehlt suchen kann, bzw. wie evtl. die Funktion heißt?

Lass es mal für steigende Werte von n durchlaufen und dir die Ergebnisse ausgeben (ruhig ein paar 100 Durchläufe). Dann kommst du sicher selbst darauf, was die Funktion macht ... (Und ja, die Funktion hat, wenn ich mich nicht vertue (ich kenne sie etwas anders) auch einen Namen(spaten))

[__blackjack__]

@Andre24HGW: Ich denke es wird eine nicht-rekursive *Funktion* erwartet. Und ich würde als Lehrer wohl auch fragen wie das zustande gekommen ist, denn das da eine `n` durch `i` ersetzt wird und das andere durch `i+1` finde ich jetzt nicht selbsterklärend. Warum kannst/darfst Du das so machen? Das ist ja nicht nach Schema aus der Rekursion eine Iteration gemacht, Du hast da an der Berechnung etwas geändert.

Und den Fall n=0 hast Du anscheinend nicht getestet.

[Andre24HGW]

Guten Morgen,

Danke für die schnellen Antworten! Top.

@nezzcarth: ich werd mal mit 100+ Durchläufe starten. Meine wenigen haben mir nicht wirklich etwas gezeigt.
@blackjack: vielen Dank für den Hinweis. Ich werde mal nach dem Schema für die Umwandlung suchen. Ich „dachte“ es reicht, wenn das Ergebnis stimmt.

Da habe ich noch etwas zu tun .

[__blackjack__]

@Andre24HGW: Es mag reichen, aber in der Regel interessiert Lehrer schon ob man weiss warum etwas funktioniert, man also etwas weiss oder gelernt hat, oder ob man zufällig durch herumprobieren auf die Lösung gekommen ist, aber nicht erklären kann warum das so funktioniert. Und bei Aufgaben in denen aus einer rekursiven Lösung eine Iterative gemacht werden sollen, geht es dem Aufgabensteller üblicherweise darum, dass man das man lernt welche Umformungsschritte man da unabhängig von der konkreten Funktion machen muss.

[nezzcarth]

Ich „dachte“ es reicht, wenn das Ergebnis stimmt.

Wenn man das systematisch testen möchte, ruft man z.B. die Funktionen für die beiden Varianten mit demselben Parameter auf und prüft, ob die beiden Ergebnisse gleich sind. Tut man das für eine sinnvoll ausgewählte Menge an Zahlen (inkl. Randfälle), stehen die Chancen ganz gut, dass die Funktionen tatsächlich äquivalent sind. Dies ist mit dem von dir gezeigten Code jedoch zur Zeit nicht möglich, da die iterative Version keine Funktion ist. Daher kannst du eigentlich auch nicht sicher sein, dass das Ergebnis stimmt.

[Andre24HGW]

Ich „dachte“ es reicht, wenn das Ergebnis stimmt.

Wenn man das systematisch testen möchte, ruft man z.B. die Funktionen für die beiden Varianten mit demselben Parameter auf und prüft, ob die beiden Ergebnisse gleich sind. Tut man das für eine sinnvoll ausgewählte Menge an Zahlen (inkl. Randfälle), stehen die Chancen ganz gut, dass die Funktionen tatsächlich äquivalent sind. Dies ist mit dem von dir gezeigten Code jedoch zur Zeit nicht möglich, da die iterative Version keine Funktion ist. Daher kannst du eigentlich auch nicht sicher sein, dass das Ergebnis stimmt.

Vielen Dank. Ich habe jetzt auch mitbekommen, dass es eine Funktion werden soll. Nun habe ich versucht diese zu entwerfen. Sieht eigentlich gut aus. Leider nicht perfekt, da bei ungeraden Startwerten der Ergbnis nicht negativ ist.

Code: Alles auswählen

def mache_etwas_1(n):
    '''Iterale Funktion von mache_etwas()'''
    ergebnis = 0
    if n == 0:
        return 4
    else:
        while n >= 0:
            ergebnis = 4/(2*n+1) + (-1**n) * ergebnis
            n = n - 1
        return ergebnis

Leider komme ich nicht darauf, wie ich das ergebnis der nächstkleineren Stufe multiplizieren kann.

Vielen Dank bisher für die Hinweise. Ich werd es mal weiter versuchen.

[Andre24HGW]

@Andre24HGW: Es mag reichen, aber in der Regel interessiert Lehrer schon ob man weiss warum etwas funktioniert, man also etwas weiss oder gelernt hat, oder ob man zufällig durch herumprobieren auf die Lösung gekommen ist, aber nicht erklären kann warum das so funktioniert. Und bei Aufgaben in denen aus einer rekursiven Lösung eine Iterative gemacht werden sollen, geht es dem Aufgabensteller üblicherweise darum, dass man das man lernt welche Umformungsschritte man da unabhängig von der konkreten Funktion machen muss.

@blackjack: Super Hinweis. Ich hatte mich vom ersten Eindruck blenden lassen. Und ich gebe dir recht, dass es wohl nicht gut ankommt, wenn ich etwas so offentlich falsches abgegeben hätte.

[__blackjack__]

@Andre24HGW: Ergebnis mit 0 zu initialisieren ist keine gute Idee, weil dann das erste (-1**n) nicht ins Ergebnis eingehen kann. Und der ``n == 0``-Fall wird auch falsch behandelt — nämlich nur wenn `n` schon am Anfang 0 war. In der rekursiven Variante tritt dieser Fall aber *immer* irgendwann ein.

[Sirius3]

@Andre24HGW: der Unterschied ist, dass Du in Deiner letzten Variante von großen n nach 0 gehst, und jeweils Ergebnis mit -1 multiplizierst, wenn Du die Rekursion aber Aufrollst, dann geht `ergebnis` von 0 bis n.
Die erste Variante war also die Richtige. Ob da (-1**i) oder (-1**(I+1)) steht, ist lustigerweise irrelevant,

Code: Alles auswählen

def mache_etwas(n):
    ergebnis = 0
    for i in range(n+1):
        ergebnis = 4/(2*i+1) + (-1**i) * ergebnis
    return ergebnis

Für i==0 ergibt sich übrigens 4/(2*0+1) also 4, der Sonderfall für n==0 ist also gar nicht nötig.

[Andre24HGW]

@Sirius3: Danke. Dann war ich ja doch nicht so dolle daneben. Ich werde mit der Funktionsvariante weiterarbeiten.
@blackjack: Die Variabel muss doch vorher initialisiert werden. Ich habe keine Idee, wie ich sie initialisieren sollte, ohne später ein Typecasting vorzunehmen. Oder ist das ein Typecasting hier die Möglichkeit?

Ich habe unabhängig davon mehrere Durchläufe gestartet. Ich kann aber noch nicht sagen, wozu diese Funktion gut sein könnte. Und eine Funktion Spaten, kann ich bisher auch nicht finden. Aber ich suche weiter. Es war ja gefordert .. versuche herauszubekommen, was sie bewirkt ...

Für alle, die mich bisher unterstützt haben - Daumen hoch. Schönes WE und bitte gesund bleiben, auch wenn sich das wie eine Floskel anhört.

[__blackjack__]

@Andre24HGW: Ja sie muss vorher initialisiert werden, aber nicht mit 0. Dazu zwingt Dich ja keiner. Warum hast Du 0 gewählt?

Dir kommt das Ergebnis für grössere n nicht irgendwie bekannt vor? Das ist nicht irgendeine Zahl die da (fast) heraus kommt, die hat eine Bedeutung in der Mathematik.

[Sirius3]

@__blackjack__: das ist eine Taylor-Reihe, mit was außer 0 sollte man sie sonst initialisieren?

[Andre24HGW]

@blackjack: Stimmt, ich kann ja auch 1 nehmen, da im 1. Durchlauf ergebnis neu zugeordnet wird. Soll das wirklich die Berechnung von PI sein? Ich habe mich gar nicht getraut. Danke!!!

[__blackjack__]

@Sirius3: Wenn ich multipliziere dann doch eher mit den neutralen Element der Multiplikation, damit da eben nicht 0 heraus kommt.

[nezzcarth]

Soll das wirklich die Berechnung von PI sein? Ich habe mich gar nicht getraut. Danke!!!

Ja, das ist eine Näherungformel für Pi und zwar (meiner Meinung nach) eine, die mit einem bestimmten Mathematiker in Verbindung steht. (ich weiß nicht, ob die Person, die die Aufgabe gestellt hat, erwartet, dass man das aus herausbekommt.) Sie konvergiert relativ langsam, sodass es schon recht viele Durchläufe braucht, bis die ersten paar Nachkommastellen richtig sind (bei 1.000.000.000 Durchläufen komme ich bei mir auf 8 richtige Stellen).

[Sirius3]

@__blackjack__: das mit der Multiplikation ist ja nur eine komisch geschriebene Version der alternierenden Summe. Und die Summe hat als neutrales Element eben 0. Dass man 1 potenziert ist dabei etwas seltsam, verständlicher wäre ›ergebnis = 4/(2*i+1) - ergebnis‹.
Die geläufige Schreibweise wäre

Code: Alles auswählen

def mache_etwas(n):
    ergebnis = 0
    for i in range(n+1):
        ergebnis += (-1)**i / (2*i+1)
    return ergebnis * 4

oder kurz:

Code: Alles auswählen

def mache_etwas(n):
    return 4 * sum((-1)**i / (2*i+1) for i in range(n+1))

könnte man natürlich auch in eine rekursive Variante umschreiben, der Aufgabensteller hat es also entweder nicht besser gewußt, oder hat absichtlich die Sache komplizierter gemacht, als nötig.

[Andre24HGW]

@ nezzcarth: Als ich nur ein paar 100 Durchläufe gestartet habe, konnte ich es noch nicht sehen. Danke!
@ Sirius3: Deine Schreibeweise kann ich "noch" nicht ganz verstehen, aber ich lasse sie mal auf mich wirken. Super, dass du auch eine kurze Variante dazu gepackt hast. Das hilft mir beim Verständnis. Ggf. und hoffentlich auch in der Zukunft.
Und, ich glaube der Aufgensteller wusste genau was er macht. Das soll uns wahrscheinlich nur herausfordern. Wenn ich dazu ein Feedback bekommen habe, werde ich es mal posten.

Super - ich glaube für mich ist das Problem erst einmal gelöst.

[nezzcarth]

@ nezzcarth: Als ich nur ein paar 100 Durchläufe gestartet habe, konnte ich es noch nicht sehen. Danke!

Ja, es gibt natürlich inzwischen effizientere Methoden, um Pi zu berechnen. Diese Methode hier ist vor allem mathematisch und historisch interessant (es wird vermutet, dass sie schon im 14. Jahrhundert bekannt war).

[Andre24HGW]

Hallo Zusammen,

nochmals vielen Dank für die Hilfestellungen. Ich habe Rückmeldung zu meinen Lösungen. Alles super. Keine Anmerkungen. Scheint so gereicht zu haben.