再帰による実装ではスタックに途中結果を保持することで木構造を葉から根に辿るような順序で加算するが、そうではなく加算の順序をスケジュールして1ずつ加算するようにすれば可能。ステートを保持するためのスタックのようなものはどうしても必要になるが、計算結果を保持する必要は無く1bitしか取らずに済む。

(define (fib-naive n)
  (if (< n 2) 1 (+ (fib-naive (- n 1)) (fib-naive (- n 2)))))

(define (fib-scheduled n)
  (define (go m prev state acc)
    (cond
      ((= m (+ n 1))
        acc)
      ((< m 2)
        (if (even? state)
          (go (+ m 1) m (quotient state 2) (+ acc 1))
          (go (+ m 2) m (quotient state 2) (+ acc 1))))
      ((= prev (- m 2))
        (if (even? state)
          (go (+ m 1) m (quotient state 2) acc)
          (go (+ m 2) m (quotient state 2) acc)))
      ((= prev (- m 1))
        (go (- m 2) m (+ (* state 2) 1) acc))
      (else
        (go (- m 1) m (* state 2) acc))))
  (go n (+ n 1) 0 0))

(display (fib-naive 30)) (newline)
(display (fib-scheduled 30)) (newline)