Ankündigung

Einklappen
Keine Ankündigung bisher.

Rekursiver Funktionsaufruf funktioniert nicht (Fakultät)

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Rekursiver Funktionsaufruf funktioniert nicht (Fakultät)

    Hi, die folgende Funktion, die das Faktorial einer Zahl erstellen soll, funkt. nicht.
    Theoretisch sieht das doch gut aus, oder?
    Bsp. 3 zur Fakultät = 3x2x1 = 6
    Die Schleife wird irgendwie einmal zu wenig durchlaufen...

    <?php
    function factorial($f) {
    if ($f >1) {
    return $f * factorial(--$f);
    }
    return 1;
    }
    $factor=3;
    echo "$factor zur Fakultät:".factorial($factor)."\n";
    ?>

    Ausgae hier ist "3 zur Fakultät:2 ", was falsch ist.
    Any ideas what's wrong?


  • #2
    Bitte nutze die [php]-Tags, und rücke deinen Code vernünftig ein, damit er lesbarer ist.

    Diese Zeile hier
    PHP-Code:
            return $f factorial(--$f); 
    ist falsch.

    --$f wird zuerst ausgewertet, so dass die Zeile im ersten Durchlauf auf 2 * factorial(2) hinausläuft.

    Mache
    PHP-Code:
            return $f factorial($f-1); 
    daraus.

    Kommentar


    • #3
      Ja, der Ausdruck $f * factorial(--$f) wird von innen nach außen ausgewertet, es muss ja auch zunächst factorial(--$f) berechnet werden, bevor die Multiplikation erfolgen kann. Zu diesem Zeitpunkt ist $f natürlich schon um 1 dekrementiert.

      Da du $f nicht weiter benötigst sollte es genügen --$f durch $f - 1 zu ersetzen

      Edit: Ninja'd
      @fschmengler - @fschmengler - @schmengler
      PHP Blog - Magento Entwicklung - CSS Ribbon Generator

      Kommentar


      • #4
        Das Problem ist, dass dein Ausdruck von rechts nach links ausgewertet würd.
        Dann bekommst du folgenden ablauf
        1. f = 3 (parameter)
        2. --f -> f ist jetzt 2
        3. factorial (2)
        4. * f (also mal 2)
        5. jetzt das gleiche mit der 2
        6. dann hast am ende 2*1

        Lösung wäre das hier:
        PHP-Code:
        <?php
        function factorial($f) {
            if (
        $f >1) {
                return 
        $f-- * factorial($f);
            }
            return 
        1;
        }
        $factor=3;
        echo 
        "$factor zur Fakultät:".factorial($factor)."\n";
        ?>
        sigpic

        Kommentar


        • #5
          Hm, tatsächlich, es geht von rechts nach links. Da war meine Erklärung falsch
          @fschmengler - @fschmengler - @schmengler
          PHP Blog - Magento Entwicklung - CSS Ribbon Generator

          Kommentar


          • #6
            Im Grund eine Mischung aus beidem ...

            Man muss die operator precedence be(tr)achten:

            ++/-- stehen ziemlich weit oben, sind also als erstes dran.

            Bei den meisten Operatoren liegt “left associativity” vor, die werden also von links nach rechts ausgewertet; ein paar aber eben auch genau andersherum.

            Kommentar


            • #7
              Zitat von Frank Beitrag anzeigen
              Das Problem ist, dass dein Ausdruck von rechts nach links ausgewertet würd.
              Das eigentlich Problem ist, das --$f Nebenwirkungen hat. Auf Implementierungsdetails wie Auswertungsreihenfolge möchte ich mich nicht verlassen. $f-1 ist daher am angebrachtesten.

              Zitat von ChrisB Beitrag anzeigen
              Man muss die operator precedence be(tr)achten:

              ++/-- stehen ziemlich weit oben, sind also als erstes dran.
              --$f wird so früh ausgewertet, weil es ausgewertet werden muss um factorial aufzurufen (um die Multiplikation ausführen zu können). Das es vor der Auswertung (besser gesagt dem Lookup) von $f ausgewertet wird halte ich für ein Implementierungsdetail.

              Zitat von ChrisB Beitrag anzeigen
              Bei den meisten Operatoren liegt “left associativity” vor, die werden also von links nach rechts ausgewertet; ein paar aber eben auch genau andersherum.
              Die Assoziativität sagt aber nichts über die Auswertungsreihenfolge der Operanden aus, sondern nur über die Auswertungsreihenfolge der Operationen. Zum Beispiel kann in
              PHP-Code:
              $a++ / $a-- / $a
              $a-- vor oder nach $a++ ausgewertet werden. Die Linksassoziativität sichert lediglich zu, das
              PHP-Code:
              ($a++ / $a--) / $a 
              berechnet wird, nicht
              PHP-Code:
              $a++ / ($a-- / $a
              Meinungen, die ich geäußert habe, sind nicht notwendigerweise meine eigenen. Abweichungen von der deutschen Rechtschreibung unterliegen dem Urheberrecht, dürfen aber unter den Bedingungen von verwendet werden

              Kommentar


              • #8
                Zitat von mimomamu Beitrag anzeigen
                --$f wird so früh ausgewertet, weil es ausgewertet werden muss um factorial aufzurufen (um die Multiplikation ausführen zu können).
                Das stimmt natürlich.

                Die Assoziativität sagt aber nichts über die Auswertungsreihenfolge der Operanden aus, sondern nur über die Auswertungsreihenfolge der Operationen. Zum Beispiel kann in
                PHP-Code:
                $a++ / $a-- / $a
                $a-- vor oder nach $a++ ausgewertet werden.
                Nein - es kommt nämlich auch noch die Linksassoziativität des Operators / hinzu.

                Left associativity means that the expression is evaluated from left to right
                Also ist in deinem Beispiel $a++ zuerst auszuwerten, dann $a--, und als letztes $a - weil sie „eine Ebene höher“ eben durch den Operator / verknüpft sind.


                Das ist natürlich mit den Operatoren ++ -- schwer nachvollziehbar, da müsste man schon einen Debugger anschmeissen (und ggf. den Ausdruck noch auf mehrere Zeilen aufteilen, um alle Operationen einzeln nachvollziehen zu können).

                Etwas einfacher nachvollziehbar wird das, wenn du statt deiner $a-Ausdrücke Funktionen einsetzt, bspw. so:
                PHP-Code:
                function f20() { echo "20 "; return 20; }
                function 
                f2() { echo "2 "; return 2; }
                function 
                f5() { echo "5 "; return 5; }

                $x f20() / f2() / f5();
                echo 
                '<br>Ergebnis ist: '.$x
                - damit wirst du immer die Ausgabe
                Code:
                20 2 5 
                Ergebnis ist: 2
                bekommen - eben weil diese Ausführungsreihenfolge explizit so definiert ist.


                Genauso ist bspw. or ein linksassoziativer Operator - und das machst du dir zu Nutze, wenn du
                PHP-Code:
                $xy mysql_query(...) or die('shit happend'); 
                schreibst.

                Wenn die „Operanden“, das sind hier mysql_query und die, in beliebiger Reihenfolge ausgewertet werden könnten, hättest du da ganz offensichtlich ein potentielles Problem - nämlich dass dein Script ggf. stirbt, obwohl es mit der Ausführung der Query gar kein Problem geben würde.
                Das ist aber nicht so, weil die Reihenfolge der Auswertung auch hier klar definiert ist - eben durch die Linksassoziativität des Operators or.

                Kommentar


                • #9
                  Zitat von ChrisB Beitrag anzeigen
                  ... eben weil diese Ausführungsreihenfolge explizit so definiert ist.
                  OK, das nächste mal teste ich vor dem Schreiben. Aber warum funktioniert dann nicht der Lösungsansatz von Prof.P? Weil $f nicht im eigentlichen Sinne ausgewertet wird?
                  Meinungen, die ich geäußert habe, sind nicht notwendigerweise meine eigenen. Abweichungen von der deutschen Rechtschreibung unterliegen dem Urheberrecht, dürfen aber unter den Bedingungen von verwendet werden

                  Kommentar


                  • #10
                    Zitat von mimomamu Beitrag anzeigen
                    OK, das nächste mal teste ich vor dem Schreiben.
                    Kein Problem - das ist doch mal eine interessante Diskussion für das Anfänger-Forum

                    Aber warum funktioniert dann nicht der Lösungsansatz von Prof.P?
                    Weil, wie schon geschrieben, diese Zeile
                    PHP-Code:
                    return $f factorial(--$f); 
                    eigentlich (beim ersten Aufruf mit dem Wert 3) als
                    PHP-Code:
                    return factorial(2); 
                    ausgewertet werden soll (bzw. müsste, damit die Funktion das gewünschte bewirken würde) - wird sie aber nicht, weil -- die höchste Priorität von den verwendeten Operatoren hat.

                    Also läuft diese Zeile effektiv auf
                    PHP-Code:
                    return factorial(2); 
                    hinaus, weil $f zu dem Zeitpunkt, wo der erste Operand der Multiplikation ausgewertet wird, bereits den Wert 2 hat, durch --$f.


                    (Noch lustiger wird es, wenn du den pre- durch den post-dekrement-Operator austauschst, also schreibst:
                    PHP-Code:
                    return $f factorial($f--); 
                    Damit bekommst du einen Fatal error: Allowed memory size of ... bytes exhausted, weil $f beim Aufruf der Funktion factorial erst „ausgelesen“ und an die Funktion übergeben, und erst anschließend dekrementiert wird - und damit wird die Funktion immer wieder rekursiv mit dem Wert 3 aufgerufen, so dass die Abbruchbedingung der Rekursion gar nicht mehr erfüllt wird.)


                    Es ist ganz nützlich, sich mit der Operatoren-Rangfolge mal in der Theorie zu beschäftigen; in der Praxis wird man meist eher zur expliziten Klammerung von Ausdrücken greifen, auch wenn diese überflüssig wäre - schließlich soll ein Script ja auch schnell verständich sein, ohne das man die Rangfolge auswendig wissen muss.

                    Kommentar


                    • #11
                      Zitat von ChrisB Beitrag anzeigen
                      Kein Problem - das ist doch mal eine interessante Diskussion für das Anfänger-Forum .
                      Allerdings, mir raucht auch gerade der Schädel Denn wenn left-associativity so funktioniert, hätte der Code im Ursprungsposting ja eigentlich funktionieren müssen. Dass die Operator-Rangfolge nicht nur die Stärke der Bindung beeinflusst sondern auch die Reihenfolge der Ausführung war mir neu, auf jeden Fall gut zu wissen!
                      @fschmengler - @fschmengler - @schmengler
                      PHP Blog - Magento Entwicklung - CSS Ribbon Generator

                      Kommentar


                      • #12
                        Dass die Operator-Rangfolge nicht nur die Stärke der Bindung beeinflusst sondern auch die Reihenfolge der Ausführung war mir neu, auf jeden Fall gut zu wissen!
                        Tut sie nicht. Die Reihenfolge bestimmt die Reihenfolge.

                        Zurück zum Beispiel:
                        PHP-Code:
                        <?php

                        function factorial($f) {
                          if (
                        $f 1) {
                            return 
                        $f factorial(--$f);
                          }

                          return 
                        1;
                        }

                        $factor=3;

                        echo 
                        "$factor zur Fakultät:".factorial($factor)."\n";

                        ?>
                        Die einzige relevante Information ist hier, dass ++$var eine Inkrementierung vor Zuweisung nach links erzeugt und $var++ erst den aktuellen Wert zuweils und danach inkrementiert.
                        --

                        „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
                        Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


                        --

                        Kommentar


                        • #13
                          Der Unterschied von ++$var und $var++ steht hier doch gar nicht in Frage (außer dass $f-- aus o.g. Gründen völlig unsinnig wäre), sondern warum factorial(--$f) vor $f ausgewertet wird.
                          @fschmengler - @fschmengler - @schmengler
                          PHP Blog - Magento Entwicklung - CSS Ribbon Generator

                          Kommentar


                          • #14
                            sondern warum factorial(--$f) vor $f ausgewertet wird.
                            Warum ist das denn relevant? Mal ist mal.
                            --

                            „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
                            Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


                            --

                            Kommentar


                            • #15
                              Weil die Funktion sonst das korrekt Ergebnis ausspucken müsste. Die Fakultät von 3 ist nun mal nicht 2.

                              So berechnet die Funktion
                              Code:
                              2 * factorial(2)
                                1 * factorial(1)
                              
                              // Ergebnis: 2 * 1
                              http://hallophp.de

                              Kommentar

                              Lädt...
                              X