Why is this recursive map function using all available memory?

I am trying to implement the map function in Python using recursion, running it on Google Colab.

def randfun(var):
    return var * 2

def mapr(f, itr):
    if len(itr) == 1:
        return f(itr[0])
    else:
        amendedlist = list(mapr(randfun, f(itr[1:])))
        #print(amendedlist)
        return amendedlist

li = [1,2,3,4,5]
result = mapr(randfun, li)
print(result)

The error I’m getting is this: Your session crashed after using all available RAM. It produces a bunch of logs, which I can’t decrypt, but am happy to reproduce.

Looks like the code is failing to halt the recursion and it goes on infinitely, but again I’m not sure. What am I doing wrong?

Answer

When you recurse, you need to pass a shorter list to mapr(), e.g. itr[1:]. But you’re passing f(itr[1:]) instead. When itr == [1, 2, 3, 4, 5], f(itr[1:]) is f([2, 3, 4, 5]) which is [2, 3, 4, 5, 2, 3, 4, 5]. So the argument is getting shorter, not longer, and you never reach the base case.

The recursion should just pass itr[1:], not f(itr[1:]) since the arguments to f() should be list elements, not the list itself.

Your base case is also wrong. mapr() must always return a list, but in the base case you’re just returning the result of the function without wrapping it into a list.

It would be best to use an empty list as the base case, so the function works for empty lists.

def mapr(f, itr):
    if len(itr) == 0:
        return []
    else:
        amendedlist = [f(itr[0])] + mapr(f, itr[1:])
        #print(amendedlist)
        return amendedlist