Recaman with recursion

Question

lst = []
def recaman(n):
  #print lst
  if n == 1:
    lst.append(n)
    return 1
  else:
    a = recaman(n-1)
    am = a - n
    ap = a + n
    if am > 0 and am not in lst:
      lst.append(am)
      return am
    else:
      lst.append(ap)
      return ap
  #print lst
  #lst.append(temp)   
#print recaman(1)
#print recaman(2)
#print recaman(3)
#print recaman(4)
#print recaman(5)
print recaman(6)
#13

This might be easy question for you but I couldn't find the explanation of this: If I print just recaman(6) The output is 13 which is true, however if i print recaman(5) and recaman(6) at the same time, the output is 7 and 11 which should have been 7 and 13. Why is this?

Answer 1

The problem is that the list is being defined globally, so after recaman is called, the next call to the function produces unexpected results because the list still has items in it:

print(recaman(5)) # 7
print(lst) # [1, 3, 6, 2, 7]

Solution

There are many possible solutions, but a simple, elegant one (in my opinion), is to make the recaman function take a list as a parameter. This list can then be passed around in the recursive calls. Initially you would call it with an empty list. So the final code becomes:

def recaman(n, lst):
  if n == 1:
    lst.append(n)
    return 1
  else:
    a = recaman(n-1, lst)
    am = a - n
    ap = a + n
    if am > 0 and am not in lst:
      lst.append(am)
      return am
    else:
      lst.append(ap)
      return ap

print(recaman(5, [])) # 7
print(recaman(6, [])) # 13