Here's my godawful Scheme solution, I can't even figure out the general case for the first two iterations, someone please help?
(define (hofstadter+ n)
(let* ((store (cons 7 's))
(tail store)
(r 7)
(s 5))
(let loop ((n n))
(unless (zero? n)
(display r)
(newline)
(set! r (+ r s))
(set-cdr! tail (cons r 's))
(set! tail (cdr tail))
(if (>= (+ 1 s) (car store))
(begin
(set! s (+ s 2))
(set! store (cdr store)))
(set! s (+ s 1)))
(loop (- n 1))))))
(define (hofstadter n)
(when (> n 1) (display "1\n"))
(when (> n 2) (display "3\n"))
(when (> n 3) (hofstadter+ (- n 2))))The space complexity is O(n) as S(n), the distance between R(n) and R(n+1), monotonously grows, meaning that it is becoming increasingly uncommon that you can discard a previously computed S(x) value.