def invert(lst): 
  if len(lst)<=1: return lst
  else:
    return invert(lst[1:]) + [lst[0]]
  
  
def build_inverted(acc, L, pos):
  acc.append(L[pos])
  if pos==0: return acc
  return build_inverted(acc,L,pos-1)
  
def invert2(L):
  inverted = []
  return build_inverted(inverted, L, len(L)-1)





def is_palindrome_cheap(s):
  return s[::-1]==s



def is_palindrome(s):
  if len(s)<2: return True
  return s[0] == s[-1] and is_palindrome(s[1:-1])

#This is the countdown gcd

def gcd_helper(m,n,d):
  if m%d==0 and n%d==0:
    return d
  return gcd_helper(m,n,d-1)

def gcd(m,n):
  return gcd_helper(m,n,min(m,n))


#this is the Euclidean Algorithm One
def gcd2(m,n):
    if m==0:  return n
    elif n==0:  return m
    else:  return gcd2(n, m % n)


def singles(L):
  if L == []: return []
  else:
    first = L[0]
    rem = L[1:]
    remaining_without_first = \
      list(filter(lambda x: x != first, rem))
    return [first] + singles(remaining_without_first)