CODEWITHSUNDEEP
pythonpython-3.xrecursion
Sania
Sania

Reputation: 93

Recaman sequence in python

I'm trying to create Recaman's sequence using recursion in python, and I am having difficulty doing so.

I understand how Recaman's sequence works. In my case, given rec(n), every nth term is equal to the previous term minus n if the value has not previously appeared in the sequence and would be equal to the previous term minus n otherwise.

My main issue with this problem would be figuring out how to somehow 'save' each rec(n) to check if it has previously appeared, and then compare the existing n to that value.

My code so far does not show much, but I believe I do have to add a parameter and use a wrapper function/accumulative recursion to get this to work.

This is my current code, it definitely does not work but I am trying to store values in a list.

def rec(n):
  list = []
  if n == 0:
    return 0
  elif rec(n-1) - n in list:
    list.append(rec(n-1) - n)
    return rec(n-1) - n
  else:
    list.append(rec(n-1) + n)
    return rec(n-1) + n

Upvotes: 0

Views: 2676

Answers (2)

Piet Hein
Piet Hein

Reputation: 1

Using assignment expressions from Python 3.8 (walrus operator) you can generate the Recaman sequence in a single line of code. Unfortunately, it takes O(x^2) time. :(

R = [0]; [(R:= R + [R[-1]+x]) if R[-1]-x in R or R[-1] < x else (R := R + [R[-1]-x]) for x in range(1,100)]

Upvotes: 0

Sahil
Sahil

Reputation: 276

If you need without recursion you can check this out:

import numpy as np

def recaman(n):
    series = np.zeros(n)
    series[0] = 0
    for i in range(1, n):
        if series[i - 1] - i > 0 and series[i - 1] - i not in series:
            series[i] = series[i - 1] - i
        else:
            series[i] = series[i - 1] + i
    return series

Upvotes: 1

Related Questions