Probleme mit Rekursion

  • geschlossen
  • C

  • Snowfire
  • 2756 Aufrufe 6 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Probleme mit Rekursion

    Hallo Leute,
    ich schreibe demnächst eine Klausur und bin fleißig am üben. Das einzige Problem sind noch die Rekursionen...
    Die Fakultät via Rekursion zu lösen, ist kein Ding aber die Aufgabe unten bereitet mir große Schwierigkeiten.
    Der b)-Teil ist mit Sicherheit machbar, wenn ich auf a) komme. Kann mir bei diesr Teilaufgabe jemand ein paar Tipps oder die Lösung geben?


    Es soll eine Funktion subtrahiere(x,y) für x,y größer gleich 0 und ganzzahlig realisiert werden, welche als Ergebnis x-y liefert, als arithmetische Operationen aber ausschließlich Addition und Subtraktion von 1 verwendet (z.B. subtrahiere(3,4) ist -1).

    a) Formulieren Sie eine rekursive Definition für diese Funktion. Schreiben Sie die
    rekursive Auswertung von subtrahiere(3,4) auf.

    b) Schreiben Sie die Funktion als rekursive Funktionsdefinition in C auf (korrektes
    Einrücken und Bezeichner aus der Aufgabenstellung).


    Schonmal vielen Dank.

    MfG,
    Snowfire

  • Hey nile,

    vielen vielen Dank, es hat nun erfolgreich geklappt.

    Leider sind die Rekursionen nicht meine stärke und ich hab schon die nächste Aufgabe wo ich häng:


    Es soll eine Funktion teilbar(t,a1,…,an) für n größer/gleich 1 und ai,t Element von N realisiert werden, die das Ergebnis wahr liefert, wenn alle ai ohne Rest teilbar durch t sind und falsch sonst (z.B. teilbar(3,15,9,27,33) ist wahr).
    a) Formulieren Sie eine rekursive Definition für diese Funktion. Schreiben Sie die
    rekursive Auswertung von teilbar(5,15,9,5,50,25) auf.


    Wie lautet hier der Triviale fall?
    Das Ganze wird bestimmt über "mod" gelöst...
    Reicht es wenn ich hier a1 bis an mod t teste und sofern hier das Ergebnis nicht 0 ist kommt "falsch" heraus?

    Schönes Wochenende,
    Snowfire

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Snowfire ()

  • Meines Wissens lässt sich eine Funktion in C gar nicht so aufbauen, bei beliebig vielen Parametern muss einer die Anzahl der Parameter enthalten, was in deinem Beispiel nicht berücksichtigt ist.

    Reicht es wenn ich hier a1 bis an mod t teste und sofern hier das Ergebnis nicht 0 ist kommt "falsch" heraus?


    Jop. Musst das ganze nur eben rekursiv formulieren.

    Wie lautet hier der Triviale fall?


    Nun, was wird denn bei jedem Rekursionsschritt gemacht? Es bietet sich an, jeweils ein Element auf modulo 0 zu prüfen und dieses Element im folgenden Funktionsaufruf wegzulassen.


    Gruß
    nile

  • Meines Wissens lässt sich eine Funktion in C gar nicht so aufbauen, bei beliebig vielen Parametern muss einer die Anzahl der Parameter enthalten, was in deinem Beispiel nicht berücksichtigt ist.


    Ich denke unser Prof ging davon aus, dass wir die Anzahl ebenfalls kennen/übernehmen.


    Jop. Musst das ganze nur eben rekursiv formulieren.


    Hier liegt bei mir immer das Problem, das ganze rekursiv zu verpacken!

    n = anzahl
    a[0] hat den Wert t
    Ich muss also folgendes testen (glaube ich):

    a[n] mod t = 0 ?
    a[n-1] mod t = 0?
    a[n-2] mod t = 0?
    .
    .
    .
    a[1] mod t = 0?

    Mein Vektor muss also nach dem testen des letzten Elements um 1 kleiner werden, sofern er durch t teilbar ist?

    Leider habe ich trotzdem keinen schimmer wie ich das rekusiv umsetze...


    Nun, was wird denn bei jedem Rekursionsschritt gemacht? Es bietet sich an, jeweils ein Element auf modulo 0 zu prüfen und dieses Element im folgenden Funktionsaufruf wegzulassen.


    n beim trivialen Fall ist 1.
    Entweder müsste er dann lauten:
    an = t -> wahr
    oder
    an mod t = 0 -> wahr



    Gruß
    nile


    Fixed ;)! Und nochmals vielen Dank für deine Hilfe!!!


  • Ich muss also folgendes testen (glaube ich):
    [...]
    Mein Vektor muss also nach dem testen des letzten Elements um 1 kleiner werden, sofern er durch t teilbar ist?

    Leider habe ich trotzdem keinen schimmer wie ich das rekusiv umsetze...


    Da gibt es mehrere Möglichkeiten. In jedem Aufruf prüfst du einen Parameter auf modulo t, abhängig vom Ergebnis gibst du dann also false zurück oder machst den nächsten rekursiven Aufruf.

    Nun musst dir nur einen Weg überlegen, wie du dir merken kannst, welchen Parameter du prüfen musst. Anbieten würde sich da spontan:

    Du prüfst, ob die Methode nur einen Parameter hat (return true), wenn nicht, dann rechnest du den letzten Parameter [an] modulo t, ist dies gleich null, rufst du die Funktion wieder auf mit teilbar(t,a1,...,an-1).

  • Ich habs endlich geschafft, nach ca. 3 Stunden ;)!
    Nochmals vielen, vielen Dank für deine Geduld und deine super Hilfe, nile!!!
    Eventuell komm ich nochmals drauf zurück.
    Ich hab jetzt noch 7 Rekursionen vor mir. Ich hoffe zwar, dass ich diese alle allein schaffen werde, aber im Notfall werd ich mich hier nochmal melden!

    Liebe Grüße,

    Snowfire