CODEWITHSUNDEEP
pythonpython-3.x
Raghav Taneja
Raghav Taneja

Reputation: 15

Recursively splitting list in half to find product of all numbers

I'm currently trying to write a recursive function which takes in two integer parameters, and must take all the values from the first to the last integer, continuously split the list in half in order to multiply each side and find the product of all the integer values. I currently have the following code typed out:

def multiply(n, m):

    lis = range(n, m)
    half = len(lis)//2
    leftSide = lis[:half]
    rightSide = lis[half+1:]
    if n == 0 or m == 0:
        return 0
    elif len(lis) == 0:
        return 0
    elif len(lis) == 1:
        return lis[0]
    return multiply(leftSide) * multiply(rightSide)

But when I run the code I get the following error:

TypeError: multiply() missing 1 required positional argument: 'm'

Any input or help of any kind would be greatly appreciated.

Upvotes: 1

Views: 1286

Answers (2)

user1532172
user1532172

Reputation:

Try something like this. You won't have to create extra memory this way. 

def multiply(lo, hi):
    if lo == hi:
        return lo
    else:
        mid = (lo + hi) // 2
        return multiply(lo, mid) * multiply(mid + 1, hi)

product = multiply(1, 4) # 1 * 2 * 3 * 4
print(product) # 24

Upvotes: 0

Karan Bhagat
Karan Bhagat

Reputation: 329

The multiply(n, m) takes two parameters n and m, but in the recursive (where you are returning in the multiply function) step you are passing a list to the multiply function. You need something like:

def multiply(myList: List[int]) -> List[int]:
if len(myList) == 0:
    return 0
elif len(myList) == 1:
    return myList[0]
half = len(myList)//2
leftSide = myList[:half]
rightSide = myList[half:]
return multiply(leftSide) * multiply(rightSide)

multiply([i for i in range(n, m+1)])

Upvotes: 1

Related Questions