Рекурсивный алгоритм последовательности recaman

Question

Где можно найти рекурсивный алгоритм для последовательности Recaman? Все опубликованные алгоритмы имеют итеративный тип. Язык не важен.

Answer 1

Вот решение в Python:

def rec(x): 
     if x == 1: 
      list.append(x) 
      return x 
     else: 
      a = rec(x-1) 
      am = a - x 
      ap = a + x 
      if am > 0 and am not in list: 
       list.append(am) 
       return am 
      else: 
       list.append(ap) 
       return ap 
list=[] 
return rec(x) 

Answer 2

В схеме можно использовать

(define (inseq seq n m) 
    (cond 
    ((= 0 n) #f) 
    (else (or (= m (seq n)) (inseq seq (- n 1) m))))) 

(define (lower n) 
    (- (rec (- n 1)) n)) 

(define (higher n) 
    (+ (rec (- n 1)) n)) 

(define (rec n) 
    (cond 
    ((= 1 n) 1) 
    ((and (> (lower n) 0) (not (inseq rec (- n 1) (lower n)))) (lower n)) 
    (else (higher n)))) 

вычислить ряд. Это рекурсивный (но неэффективный и очень неэлегантный), как написано.

Answer 3

Я лично считаю этот вопрос очень интересный сам по себе.

Во-первыхи, чистый (т.е. без побочных эффектов) рекурсивная реализация в Python:

def recaman_sequence(n): 
    def recurs(seen, i, term): 
     if i > n: 
      return [] 
     elif term > i and term - i not in seen: 
      return [term - i] + recurs(seen.union({term - i}), i + 1, term - i) 
     else: 
      return [term + i] + recurs(seen.union({term + i}), i + 1, term + i) 
    return recurs(set(), 1, 0) 

В языке с оптимизацией хвостового вызова, как OCaml, быстрее реализацией может быть по этим направлениям:

Обратите внимание, что List.mem - O (n). Более продвинутая версия будет использовать отдельный аккумулятор с этой операцией в O (log n) или O (1) (например, set в Python).

OEIS имеет такую ​​версию в Haskell, очень читаемый, но опять-таки не хвостовой рекурсией (из-за Reinhard Zumkeller, 14 марта 2011):

import Data.Set (Set, singleton, notMember, insert) 
a005132 n = a005132_list !! n 
a005132_list = 0 : recaman (singleton 0) 1 0 where 
    recaman :: Set Integer -> Integer -> Integer -> [Integer] 
    recaman s n x = if x > n && (x - n) `notMember` s 
         then (x-n) : recaman (insert (x-n) s) (n+1) (x-n) 
         else (x+n) : recaman (insert (x+n) s) (n+1) (x+n)