Odd question relating to project euler 72 (lisp)

Question

I recognize that there's an obvious pattern in the output to this, I just want to know why lispbox's REPL aborts when I try to run anything > 52. Also, any suggestions on improving the code are more than welcome. ^-^

(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)))))

All I get when I call

(count-reduced-fractions 53 53 0)

is

;Evaluation aborted

It doesn't make much sense to me, considering it'll run (and return the accurate result) on all numbers below that, and that I could (if i wanted to) do 53 in my head, on paper, or one line at a time in lisp. I even tested on many different numbers greater than 53 to make sure it wasnt specific to 53. Nothing works.

Answer 1

Probably a Stack Overflow (heh).

Answer 2

My guess is that there's a built-in stack depth limit with lispbox. Since Common Lisp does not guarantee tail-recursive functions use constant stack space, it's possible that every invocation of count-reduced-fractions adds another layer on the stack.

By the way, SBCL runs this algorithm without problem.

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

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

Answer 3

As a matter of style, you could make d and sum optional.

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

Answer 4

This behaviour hints at a missing tail call optimization, so that your recursion blows the stack. A possible reason is that you have declaimed debugging optimization.

By the way, you don't need to make an explicit call to return-from. Since sum is a self-evaluating symbol, you can change this line

(return-from count-reduced-fractions sum)

to

sum

edit: Explanation of the proposed change: "sum" evaluates to its own value, which becomes the return value of the "if" statement, which (since this is the last statement in the defun) becomes the return value of the function.

edit: Explanation of declaimed optimization: You could add the following to your top level:

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

or use the same, but with declare instead of declaim as the first statement in your function. You could also try (space 3) and (safety 0) if it doesn't work.

Tail call optimization means that a function call whose return value is directly returned is translated into a frame replacement on the stack (instead of stacking up), effectively "flattening" a recursive function call to a loop, and eliminating the recursive function calls. This makes debugging a bit harder, because there are no function calls where you expect them, resp. you do not know how "deep" into a recursion an error occurs (just as if you had written a loop to begin with). Your environment might make some default declamations that you have to override to enable TCO.

edit: Just revisiting this question, what is g? I think that you actually want to

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