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)