Converting iterative fuction to recursion-CodePudding

I'm trying to convert this iterative function into a recursive function. The function accepts an integer x and list of integers. The for loop removes an element of the list

def function(x, arr):
  for v in arr:
    if v % x == 0:
      arr.remove(v)
  return arr

I tried doing this but it seems it does not work:

out = []
def removeMultiples(x, arr):
  if len(arr) < 1:
    return arr
  else:
    if arr[0] % x == 0:
      out.append(arr[0])
      return out   removeMultiples(x, arr[1:])
    else:
      return out   removeMultiples(x, arr[1:])

CodePudding user response：

The iterative version of this function could use a list comprehension

def function(x, arr):
    return [i for i in arr if i % x != 0]

and the recursive version could look something like this

def removeMultiples(x, arr):
    if not arr:
        return []
    current, rest = arr[0], arr[1:]
    if current % x != 0:
        return [current]   removeMultiples(x, rest)
    else:
        return removeMultiples(x, rest)

for example

>>> values = [1,2,3,4,5,6,7,8]
>>> function(2, values)
[1, 3, 5, 7]
>>> removeMultiples(2, values)
[1, 3, 5, 7]

Note that both of these versions create and return a new list, rather than removing elements from your existing list.

CodePudding user response：

You can make your function process the first element and recurse for the rest until there are no more elements in the list.

def removeMultiples(x,arr):
    return arr[:1]*bool(arr[0]%x)   removeMultiples(x,arr[1:]) if arr else []

r = removeMultiples(3,[2,5,6,4,12,7])
print(r)
[2, 5, 4, 7]

If you prefer a more elaborate solution that avoids Python's recursion depth limit and doesn't make copies of the list, you can work with subranges and split the list down the middle to recurse twice, eliminating multiples of x on the left and right side. Then put the two cleaned up sides together:

def removeMultiples(x,arr,start=0,end=None):
    if end is None: end = len(arr)
    if end-start <= 1: 
        return arr and arr[start:end]*bool(arr[start]%x)
    mid = (start end)//2
    return removeMultiples(x,arr,start,mid)   removeMultiples(x,arr,mid,end)