Infinite Recursion in Python Function if Argument Too Long

Question

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?

why do you think that there is an infinite recursion happening? — Aida Paul
– Aida Paul, Commented Feb 26, 2014 at 1:35
Someone else will answer this sort of question conclusively quicker than I can, but I have to ask: have you put print statements in it to see what it's doing? Surely that would tell you the answer? — GreenAsJade
– GreenAsJade, Commented Feb 26, 2014 at 1:36

Andrew Clark · Accepted Answer · 2014-02-26 01:40:59Z

2

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.

answered Feb 26, 2014 at 1:40

Andrew Clark

210k36 gold badges286 silver badges310 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Roberto Over a year ago

I'm a newbie and never encountered something like def max_r(l: [int]) -> int: in Python. Where can I find more about it?

Andrew Clark Over a year ago

@Roberto I'm actually not sure, but it is likely some modified interpreter or an editor that allows you to give type hints for better static analysis and/or code completion.

kelm Over a year ago

It's perfectly valid Python 3 syntax. These are called annotations, and you can read about them in the docs: docs.python.org/3/reference/…

Hugh Bothwell Over a year ago

To clarify: the function was calling itself twice at each step, for a total of 2 ** len(lst) - 1 calls. F.J's modification only calls once at each step, for a total of len(lst) - 1 calls. On the sample data, that is 46 function calls instead of 140.7 trillion calls.

GreenAsJade Over a year ago

... which would have immediately been apparent with some basic instrumentation aka print statements ;)

|

Collectives™ on Stack Overflow

Infinite Recursion in Python Function if Argument Too Long

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related