CODEWITHSUNDEEP
pythonpython-3.xrecursion
austinsherron
austinsherron

Reputation: 163

Infinite Recursion in Python Function if Argument Too Long

I wrote this recursive function that returns the largest value in a list of integers:

def max_r(l: [int]) -> int:
    if len(l) == 1:
        return l[0]
    else:
        return l[0] if max_r(l[1:]) < l[0] else max_r(l[1:])

The call max_r([1,4,3,2,3,4,89,2,30,1] returns 89, but calling the function on a longer list:

max_r([96, 84, 87, 81, 94, 74, 65, 42, 45, 76, 5, 37, 86, 8, 46, 54, 62, 63, 35, 85, 16, 23, 18, 57, 51, 90, 58, 33, 47, 10, 64, 49, 67, 29, 71, 30, 9, 99, 75, 3, 97, 32, 59, 25, 27, 72, 61])

results in infinite recursion. Why?

Upvotes: 3

Views: 285

Answers (1)

Andrew Clark
Andrew Clark

Reputation: 208485

It isn't infinitely recursive, but you are doing the same recursive call twice when you don't need to. Seems to complete quickly enough with the following change:

def max_r(l: [int]) -> int:
    if len(l) == 1:
        return l[0]
    else:
        result = max_r(l[1:])
        return l[0] if result < l[0] else result

This isn't just a matter of calling the function recursively twice as many times, I'm not sure on the exact growth rate but it seems be exponential since each extra recursive call will be making more extra recursive calls.

Upvotes: 2

Related Questions