Seltsame Frage zum Projekt euler 72 (lisp)

Question

Ich erkenne, dass es ein offensichtliches Muster in der Ausgabe dazu gibt, ich möchte nur wissen, warum die REPL von Lispbox abbricht, wenn ich versuche, etwas > 52 auszuführen. Außerdem sind alle Vorschläge zur Verbesserung des Codes mehr als willkommen. ^-^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

Alles, was ich bekomme, wenn ich anrufe

(count-reduced-fractions 53 53 0)

ist

Auswertung abgebrochen

Es macht nicht viel Sinn für mich, wenn man bedenkt, dass es auf allen Zahlen darunter läuft (und das genaue Ergebnis zurückgibt), und dass ich (wenn ich wollte) 53 in meinem Kopf, auf Papier oder eine Zeile nach der anderen in Lisp machen könnte. Ich habe sogar viele verschiedene Zahlen größer als 53 getestet, um sicher zu gehen, dass es nicht spezifisch für 53 ist. Nichts funktioniert.

Answer 1

Dieses Verhalten deutet auf eine fehlende Tail-Call-Optimierung hin, so dass Ihre Rekursion den Stack sprengt. Ein möglicher Grund ist, dass Sie die Debugging-Optimierung deklariert haben.

Übrigens müssen Sie nicht explizit einen Aufruf an return-from . Seit sum ein selbstbewertendes Symbol ist, können Sie diese Zeile ändern

(return-from count-reduced-fractions sum)

zu

sum

éditer : Erläuterung der vorgeschlagenen Änderung: "sum" wird zu seinem eigenen Wert ausgewertet, der zum Rückgabewert der "if"-Anweisung wird, die (da dies die letzte Anweisung in der defun-Anweisung ist) zum Rückgabewert der Funktion wird.

éditer : Erläuterung der deklarierten Optimierung: Sie könnten Folgendes zu Ihrer obersten Ebene hinzufügen:

(declaim (optimize (speed 3)
                   (debug 0)))

oder verwenden Sie dasselbe, aber mit declare anstelle von declaim als erste Anweisung in Ihrer Funktion. Sie könnten auch (Leerzeichen 3) und (Sicherheit 0) ausprobieren, wenn es nicht funktioniert.

Tail-Call-Optimierung bedeutet, dass ein Funktionsaufruf, dessen Rückgabewert direkt zurückgegeben wird, in einen Frame-Ersatz auf dem Stack übersetzt wird (statt aufzustapeln), wodurch ein rekursiver Funktionsaufruf effektiv zu einer Schleife "verflacht" wird und die rekursiven Funktionsaufrufe eliminiert werden. Das macht die Fehlersuche etwas schwieriger, da es keine Funktionsaufrufe an den Stellen gibt, an denen man sie erwartet, bzw. man nicht weiß, wie "tief" in einer Rekursion ein Fehler auftritt (genauso, wie wenn man zu Beginn eine Schleife geschrieben hätte). Ihre Umgebung könnte einige Standarddeklarationen vorsehen, die Sie überschreiben müssen, um TCO zu aktivieren.

éditer : Um auf diese Frage zurückzukommen, was ist g ? Ich denke, dass Sie tatsächlich wollen

(let ((g (gcd n d)))
  ;; ...
  )

Answer 2

Ich vermute, dass es bei Lispbox eine eingebaute Begrenzung der Stapeltiefe gibt. Da Common Lisp nicht garantiert, dass tail-recursive Funktionen konstanten Stackplatz verwenden, ist es möglich, dass jeder Aufruf von count-reduced-fractions eine weitere Schicht auf dem Stack hinzufügt.

SBCL führt diesen Algorithmus übrigens ohne Probleme aus.

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043

Answer 3

Aus stilistischen Gründen könnten Sie d und sum fakultativ machen.

(defun test (n &optional (d n) (sum 0)) .. )

Answer 4

Wahrscheinlich ein Stack Overflow (hehe).