Q:

How to speed up recursive call on Python linked list?

I have recursive function named min_max; it is passed a linked list; it returns a 2-tuple containing the minimum value followed by the maximum value. If the linked list is empty, then min_max returns (None, None). For example, if we called this function as min_max(list_to_ll([1, 3, 7, 2, 0])) the returned result would be (0, 7).
class LN:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def min_max(ll):
    if ll == None:
        return (None,None)
    else:
        result = (ll.value,ll.value)
        if ll.next != None:
            return (min(result[0],min_max(ll.next)[0]),max(result[1],min_max(ll.next)[1]))
        else:
            return result

if __name__ == '__main__':

    print('\nTesting min_max')
    print(min_max(None))
    print(min_max(list_to_ll([0])))
    print(min_max(list_to_ll([7, 3, 5, 2, 0])))
    print(min_max(list_to_ll([1, 3, 5, 2, 7])))

    values = [i for i in range(1,100)]
    print(values)
    print(min_max(list_to_ll(values)))

My question is how do I speed up my recursive call min_max on the linked list with probably 100 elements? I can pass the test_case for linked with 5-7 elements but with 100 elements my function is not efficient. Thanks. 

A:

Currently, this line:
return (min(result[0],min_max(ll.next)[0]),max(result[1],min_max(ll.next)[1]))

calls min_max recursively twice to get the minimum and maximum - this means you make 2**n calls to min_max instead of n, which is a huge penalty. Instead, consider:
min_, max_ = min_max(ll.next) # call once
return min(min_, ll.value), max(max_, ll.value) # use the two values

