[racket] Puzzled with tail-recursion conversion

From: namekuseijin (namekuseijin at gmail.com)
Date: Wed Feb 15 13:30:55 EST 2012

Hello, this is not really racket-related, for I get same issue with
larceny, for instance.  I saw a function at reddit and tried reworking
it into tail-recursion, but it baffles me why last version shouldn't
work.

; original function: works
(define pi
  (lambda (accuracy)
    (letrec ((helper
              (lambda (k accuracy)
                (let ((this (* (/ (expt -1 k) (expt 4 k))
                               (+ (/ 2 (+ (* 4 k) 1))
                                  (/ 2 (+ (* 4 k) 2))
                                  (/ 1 (+ (* 4 k) 3))))))
                  (if (< (abs this) accuracy)
                      this
                      (+ this (helper (+ k 1) accuracy)))))))
      (helper 0 accuracy))))

; more conventional define, removed redundant accuracy parameter in
helper and defined formula: works
(define (pi2 accuracy)
  (define (formula k)
    (* (/ (expt -1 k) (expt 4 k))
       (+ (/ 2 (+ (* 4 k) 1))
          (/ 2 (+ (* 4 k) 2))
          (/ 1 (+ (* 4 k) 3)))))
  (letrec ((helper
            (lambda (k)
              (let ((this (formula k)))
                (if (< (abs this) accuracy)
                    this
                    (+ this (helper (+ k 1))))))))
    (helper 0)))

; got rid of letrec and used named let: works
(define (pi3 accuracy)
  (define (formula k)
    (* (/ (expt -1 k) (expt 4 k))
       (+ (/ 2 (+ (* 4 k) 1))
          (/ 2 (+ (* 4 k) 2))
          (/ 1 (+ (* 4 k) 3)))))
  (let helper ((k 0))
    (let ((this (formula k)))
      (if (< (abs this) accuracy)
          this
          (+ this (helper (+ k 1)))))))

; reworked helper to get 1 extra parameter so that it's now
tail-recursive: doesn't work.  It simply hangs in there
indefinitely...
(define (pi4 accuracy)
  (define (formula k)
    (* (/ (expt -1 k) (expt 4 k))
       (+ (/ 2 (+ (* 4 k) 1))
          (/ 2 (+ (* 4 k) 2))
          (/ 1 (+ (* 4 k) 3)))))
  (let helper ((k 1) (this (formula 0)))
    (if (< (abs this) accuracy)
        this
        (helper (+ k 1) (+ this (formula k))))))

; any ideas?

Posted on the users mailing list.