Recaman's sequence recursive algorithm

Question

Where can I find recursive algorithm for Recaman's sequence? All algorithms published are of iterative type. Language is not important.

Here are the typical clarifying questions you should use to improve your question. What are you trying to do? What have you tried? Why does it need to be recursive instead of iterative? Why can't you just convert the iterative algorithm to a recursive one yourself? Why do you need code, but are language agnostic? Therefore, this question is too broad so I'll be flagging it unless/until you edit it to clarify and improve the question — Kevin, Feb 24 '16 at 20:34
I agree to Kevin Wells but still I find the topic very interesting. The difficulty here is that the recursion rule depends on all previous numbers in the sequence. — Frank Puffer, Feb 24 '16 at 21:26
Here is a long list of recursive code implementations that generate the sequence https://rosettacode.org/wiki/Recaman%27s_sequence — Charlie Wallace, Feb 18 '19 at 15:54

score 1 · Accepted Answer · answered Feb 24 '16 at 22:13

1

Here is a solution in 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)

answered Feb 24 '16 at 22:13

jurij

383
3
7
21

1

Nice, but does this count as a recursive algorithm, operating on the global list? At least I would find it more elegent to pass the array (or a reference to it) as an additional argument. – Frank Puffer Feb 25 '16 at 21:21

Aristide · Answer 2 · 2018-03-11T10:00:44.633

I personally find this question quite interesting by itself.

First, a pure (i.e. without side effects) recursive implementation in 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)

In a language with tail-call optimization, like OCaml, a faster implementation could be along these lines:

let recaman_sequence n =
    let rec urs i = function
        | [] -> urs (i + 1) [1]
        | terms when i > n -> List.rev terms
        | term::tail as terms when term > i && not (List.mem (term - i) tail) -> urs (i + 1) ((term - i)::terms)
        | term::tail as terms -> urs (i + 1) ((term + i)::terms)
    in urs 1 []
;;

Note however that List.mem is O(n). A more advanced version would use a separated accumulator with this operation in O(log n) or O(1) (like set in Python).

OEIS has such a version in Haskell (due to Reinhard Zumkeller, Mar 14 2011), very readable, but again not tail-recursive:

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)

The first (Python) proposed solution fails if `n>996` with `RecursionError: maximum recursion depth exceeded in comparison` raised. — Adrian Chrostowski, Apr 05 '20 at 10:11
@AdrianChrostowski you may give a look to https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it on this site. — Aristide, Apr 05 '20 at 10:48

score 0 · Answer 3 · answered Feb 24 '16 at 21:01

In scheme you can use

 (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))))

to calculate the series. This is recursive (but inefficient and very inelegant) as written.

Recaman's sequence recursive algorithm

3 Answers3