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）（如Python中的set）中，更高級的版本將使用此操作的單獨累加器。

OEIS在哈斯克爾，可讀性很強這樣一個版本，但同樣不是尾遞歸（由於萊因哈德Zumkeller，2011年3月14日）：

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)