Recamán's Sequence in Racket

Question

I just started learning Racket as my first lisp dialect so after getting used to the syntax I implemented the Recamán's sequence.

Apart from the style, I'd also like to know if my code is a linear iteration or not. I kind of get the idea but I don't know how to be sure it is.

#lang racket

(define (recaman-seq size)
  (define (recaman-iter curr-seq n goal)
    (if (= n goal)
        (reverse curr-seq)
        (cond
          [(and (= n 0) (empty? curr-seq))
           (recaman-iter (list n) (+ n 1) goal)]
          [else
           (define a (- (car curr-seq) n))
           (define b (+ (car curr-seq) n))
           (define is-new (not (member a curr-seq)))
           (cond
             [(and (positive? a) is-new)
              (recaman-iter (list* a curr-seq) (+ n 1) goal)]
             [else
              (recaman-iter (list* b curr-seq) (+ n 1) goal)])])))
  (recaman-iter '() 0 (+ size 1)))

(recaman-seq 10)

Answer 1

This code is not exactly linear as member is a o(n) time function and grown in proportion to curr-seq, making the whole function about O(n^2).

However without an algorithmic trick, the function requires a search of past results, and the best search that I know of on a mutable structure is O(log (n)), so the best you can hope for here is O(n*log(n)). But this is only if you go off to infinity.

This sequence seems reasonably dense, so you could probably create a boolean vector a bit bigger than the sequence initialized to true,and as you add numbers to the sequence flip the value of that index to false.

First to translate to scheme...

(define (recaman-seq size)
  (define (recaman-iter curr-seq n goal)
    (if (= n goal)
        (reverse curr-seq)
        (cond
          ((and (= n 0) (null? curr-seq))
           (recaman-iter (list n) (+ n 1) goal))
          (else
           (let* ((a      (- (car curr-seq) n))
                 (b      (+ (car curr-seq) n))
                 (is-new (not (member a curr-seq))))
           (cond
             ((and (positive? a) is-new)
              (recaman-iter (cons a curr-seq) (+ n 1) goal))
             (else
              (recaman-iter (cons b curr-seq) (+ n 1) goal))))))))
  (recaman-iter '() 0 (+ size 1)))

(recaman-seq 10) ]=>(0 1 3 6 2 7 13 20 12 21 11)

Next making some modifications, using a let to make a temperary vector, changing the define and call with a named loop,

;lang rsr5

(define (recaman-seq size)
 (let ((rman-vect (make-vector (* 10 size) #t))) 
;;hopefully generous enough
  (let recaman-iter ((curr-seq '()) (n 0))
;; goal is unneccesary, if and cond are essentially the same, nest them
    (cond ((> n size)
           (reverse curr-seq))
          ((and (= n 0) (null? curr-seq) (vector-ref rman-vect 0))
           (vector-set! rman-vect 0 #f)
;;Mark number as used, this is a side effect,not a returned value
           (recaman-iter (cons n curr-seq) (+ n 1)))
          (else
           (let* ((a      (- (car curr-seq) n))
                 (b      (+ (car curr-seq) n)))
             (cond ((and (> a 0))  (vector-ref rman-vect a)
                    (vector-set! rman-vect a #f) 
                    (recaman-iter (cons a curr-seq) (+ n 1)))
             (else (vector-set! rman-vect b #f)
                   (recaman-iter (cons b curr-seq) (+ n 1))))))))))

Can get the first 500,000 terms that way before I run out of memory.