Python code to find the max values via recursive

Question

I have a question about my Python code to find the max value within a list. The functional code is as following:

def large(x):
    if len(x) == 1:
        return x.pop(0)
    else:
        temp = x.pop(0)
        previous = large(x)
        if previous >= temp:
            return previous
        else:
            return temp

But before that, I tried:

def large(x):
    if len(x) == 1:
        return x.pop(0)
    else:
        temp = x.pop(0)
        if large(x) >= temp:
            return large(x)
        else:
            return temp

And it will return the error message as:

<ipython-input-74-dd8676a7c4e6> in large(x)
      3         return x.pop(0)
      4     else:
----> 5         temp = x.pop(0)
      6         if large(x) >= temp:
      7             return large(x)

IndexError: pop from empty list

The toy data would be:

inputlist = [6,1,3,2,3,4,5,6]
large(inputlist)

Thank you for your help in advance. I can't find the main cause of this error. As for me, these two codes are completely same.

Answer 1

The problem with

if large(x) >= temp:
    return large(x)

is that you end up calling large(x) (and therefore pop) more than once, which is removing elements from the list.

Personally, I would more go for this style than using a mutating function like pop.

def large(x):
    if len(x) == 1:
        return x[0]
    remainder = large(x[1:])
    return x[0] if x[0] > remainder else remainder

Answer 2

The same solution as OneCricketeer's but without creating list slices upon every recursive call unnecessarily. It also handles an empty list.

def large(x):
    def rec(y):
        try:
            v = next(y)
        except StopIteration:
            return None
        r = rec(y)
        if r is None:
           return v
        return v if v > r else r
    return rec(iter(x))

inputlist = [6,1,3,2,3,4,5,6]
print(large(inputlist))
print(large([]))

which produces

6
None

Answer 3

Since this is a recursion exercise, and not something we'd do in system code, I'd go with descriptive code over efficient code and do something like:

def largest(array):
    if array:
        head, *tail = array

        if tail and head < (result := largest(tail)):
            return result

        return head

    return None

if __name__ == "__main__":
    from random import choices

    array = choices(range(100), k=10)

    print(array, '->', largest(array))

OUTPUT

> python3 test.py
[46, 67, 0, 22, 23, 20, 30, 7, 87, 50] -> 87
> python3 test.py
[83, 77, 61, 53, 7, 65, 68, 43, 44, 47] -> 83
> python3 test.py
[36, 99, 47, 93, 60, 43, 56, 90, 53, 44] -> 99
> 

If you really need to be efficient, I'd recommend doing so safely. Specifically, not exposing an API with special arguments that the caller is not supposed to use, e.g.:

def my_max(lst, m=None, i=0):

As they can supply values for these extra arguments that will make your code fail, and ultimately blame it on you. Ditto for exposing internal functions that the caller might call instead of the intended one:

def my_max(lst, m=None, i=0):

def my_max_helper(lst, i):

Accidentally calling my_max_helper() with a bogus value for the poorly named i argument. Instead, I'd consider nesting your functions to avoid such calling errors:

def largest(array):

    def largest_recursive(array, index):
        a = array[index]

        if len(array) - index != 1:
            if (b := largest_recursive(array, index + 1)) > a:
                return b

        return a

    if array:
        return largest_recursive(array, 0)

    return None

Answer 4

This does not answer why the original is incorrect. Rather, it lays down a 'standard pattern' that can be used for implementing a number of recursive problems.

I am wondering that how should I eliminate the number of elements in each round with index rather than pop?

Don't "eliminate" the elements :-)

Many recursive-friendly problems operate by reducing the range each step. This includes finding the max value (or any operation that can be expressed as a fold), a binary search, a top-down merge sort, etc. Many of these problems are themselves expressed in pseudo-code using arrays and sub-problem reduction by adjusting the ranges of each recursive call. In the case of a max/binary-search this also avoids any mutations to the original object.

Thus, a recursive max function can written as the following. Note that this form of passing in the working state is Tail-Call Friendly. While I find this form is easier to express certain problems, it does not really matter in Python as [C]Python does not support Tail-Call Optimizations^{^}.

def my_max(lst, m=None, i=0):
  # base-case: return result of work
  if len(lst) == i:
    return m
  # Compute max through here
  c = lst[i]
  m = c if m is None or c > m else m
  # Call recursive function increasing the index by 1.
  # This is how the problem advances.
  return my_max(lst, m, i + 1)

The above example also use default arguments instead of a helper method. Here is an alternative that uses the recursive result — which is often how recursive functions are introduced — as well as a discrete helper method.

def my_max(lst):
  # Wrapper can ensure helper pre-conditions.
  # In this case that is a non-Empty list per the base case check.
  if not lst:
    return None
  return my_max_helper(lst, 0)

def my_max_helper(lst, i):
  # base case: last item in list returns itself
  if len(lst) - 1 == i:
    return lst[i]
  c = lst[i]
  m = my_max_helper(lst, i + 1)
  return c if c > m else m

In both cases temporarily variables are used to avoid duplicate expressions; while sometimes merely a stylistic choice, this consistency would have mitigated the original issue due to avoiding the unexpected side-effect of additional pop-mutation.

The above methods should be called with a list or other sequence that supports O(1) indexed lookups. In particular, the 'index' approach is not suitable, and will not work with, generator objects. There are other answers that cover this — just beware to avoid potential list slices like h,*t=l or l[1:] which can lead to bad performance bounds.

^{^}There are modules in Python which can emulate TCO through spring-boarding.