Geek asks and answers

Infinite recursion in a Python function if the argument is 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 calls the function in 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])

leads to infinite recursion. Why?

+3
source share
1 answer

This is not infinitely recursive, but you make the same recursive call twice when you don't need it. It seems fast enough to make the following changes:

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 is not just a function call recursively twice as large, I’m not sure about the exact growth rate, but it seems exponential, since every emergency recursive call will make more emergency recursive calls.

+2

More articles:


All Articles