Python: Recursive function to find the largest number in the list

Question

I'm trying to do a lab work from the textbook Zelle Python Programming

The question asked me to "write and test a recursive function max() to find the largest number in a list. The max is the larger of the first item and the max of all the other items." I don't quite understand the question from the textbook.

def Max(list):
    if len(list) <= 1:
        else:
            return list[0]
        else:
            m = Max(list[1:])
            return m if m > list[0] else list[0]

def main():
    list = eval(raw_input(" please enter a list of numbers: "))
    print("the largest number is: ", Max(list))

main()

Or maybe I'm suppose to open a txt file with numbers in it and then use recursive?

I believe recursive works like this

def function()
> if something:
>>return 0
>else:
>>return function()

Answer 1

I post a different solution approach of the problem. Most of the answers manipulate the list using the slice operator in each recursive call. By the time the exercise does not provide a strict function prototype to be used, I also pass as function parameter the length of the list.

Suppose that we try to find and return the maximum element from a sequence S, of n elements.

Function prototype: Max(S, n)

Base case: If S contains only one item, return it. (Obviously the only item in the sequence is the max one.)

Recur: If not the base case, call Max each time for one less item, that is call Max(S, n-1). We then store the returning value to a variable called previous that indicate the previous element from the sequence and check that value with the next element in the sequence, which is the right most element in the current recursive call, and return the max of these values.

A recursion trace of the above procedure is given in the following figure. Suppose we try to find the max from a list that contains [5, 10, 20, 11, 3].

Note: To help you further, keep in mind that we recursively iterate the list from the right most element to the left most one.

Finally here is the working code:

def find_max_recursively(S, n):                                                
    """Find the maximum element in a sequence S, of n elements."""             
    if n == 1:  # reached the left most item                                   
        return S[n-1]                                                          
    else:                                                                      
        previous = find_max_recursively(S, n-1)                                
        current = S[n-1]                                                       
        if previous > current:                                                 
            return previous                                                    
        else:                                                                  
            return current                                                     


if __name__ == '__main__':                                                     
    print(find_max_recursively([5, 10, 20, 11, 3], 5)) 

Note: The recursive implementation will work by default only with sequences of 1000 most elements.

To combat against infinite recursions, the designers of Python made an intentional decision to limit the overall number of function activations that can be simultaneously active. The precise value of this limit depends upon the Python distribution, but a typical default value is 1000. If this limit is reached, the Python interpreter raises a RuntimeError with a message, maximum recursion depth exceeded.

Michael T. Goodrich (2013), Data Structures and Algorithms in Python, Wiley

To change the default value do:

import sys
sys.setrecursionlimit(1000000)

Answer 2

here is one more approach to solve above problem

def maximum(L):
    if len(L) == 1:
        return L[0]
    else:
        return max(L[0],maximum(L[1:]))

so example input and output:

L= [2,4,6,23,1,46]
print maximum(L)

produces

46

Answer 3

The basic approach is this.

1. If the list contains only a single element, that element is the max. Return it immediately.
2. Otherwise, the list contains multiple elements. Either the first element in the list is the maximum, or it is not.
3. The maximum of the first element is simply the first element in the list.
4. Recursively call Max on the rest (all but first element) to find the maximum of those elements.
5. Compare the results from step 3 and 4. The result is the number that is greater. Return it.

Right now you have some syntax errors. For example, you have two else clauses for a single if, and the indentation looks funny. You can only have one else for an if block. But if you follow these instructions, you should have a working algorithm.

Answer 4

def Max(lis,maxx=-float("inf")):

    if len(lis) == 1:            #only one element in lis
        return maxx if maxx>lis[0] else lis[0]  #return lis[0] if it's greater than maxx

    else:
        m=lis[0] if lis[0]>maxx else maxx  # m = max(lis[0],maxx)
        return Max(lis[1:],m)              #call Max with lis[1:] and pass 'm' too

print Max([1,2,39,4,5,6,7,8]) #prints 39
print Max([1,2,3,4,5,6,7,8]) #prints 8   

Answer 5

These solutions fail after certain list size.

This is a better version:

def maximum2(a, n):
    if n == 1:
        return a[0]
    x = maximum2(a[n//2:], n - n//2)
    return x if x > a[0] else a[0]
def maximum(a):
    return maximum2(a, len(a))

maximum(range(99999))


>>> 99998

Answer 6

One simple way would be to sort the list first then use indexing.

Here's a function that would work:

a = [1,233,12,34]

def find_max(a):
    return sorted(a)[-1]

Answer 7

def find_max(arr):
  """find maximum number in array by recursion"""
  if arr == []: # if its an empty array
    return 0
  if len(arr) == 1: # if array has only one element
    return arr[0]
  else: # get max of first item compared to other items recursively
    return max(arr[0], find_max(arr[1:])) # 1: means all other excluding 0th element

def main():
  print(find_max([2,3,5,6,7,1])) # will print max - 7

if __name__ == "__main__":
  main()

Answer 8

You can also do it in this way:

def maximum(data, start, stop):

    if start >= stop:
            return data[start]

    else:
            if data[start] >= data[stop - 1]:
                return maximum(data, start, stop - 1)

            else:
                return maximum(data, start + 1, stop)

Answer 9

def recursiveMax(a):
    if len(a) == 1:
        return a[0]
    else:
        return a[0] if a[0] > recursiveMax(a[1:]) else recursiveMax(a[1:])

Test:

print(recursiveMax([1, 2, 15, 6, 3, 2, 9]))
print(recursiveMax([98, 2, 1, 1, 1, 1, ]))

Answer 10

TLDR; This code will also work when the list passed to the function is empty!

---

@jam's answer is amazing. However, I found some problems with the conditions, I think @Blender was hinting at it.

That code will fail in the case when the list passed to the function is empty. There are two base cases:

• When the list is empty -> return None
• When the list has one item -> return list[0]

And then the recursive case ... to reduce any other case into the base case.

def recursive_max(arr):
    if len(arr) == 0:
        return None
    elif len(arr) == 1:
        return arr[0]
    else:
        maxItem = recursive_max(arr[1:])
        return maxItem if maxItem > arr[0] else arr[0]

Answer 11

def find_max(my_list, max):
    if len(my_list) <= 1:
        return max
    else:
        if my_list[0] > max:
            return find_max(my_list[1:], my_list[0])
        else:
            return find_max(my_list[1:], max)

if __name__ == '__main__':
   my_list = [1, 5, 16, 9, 20, 40, 5]                                           
   print(find_max(my_list, my_list[0]))

Answer 12

Here is my answer, with a one line of code :))

def max_value(n_list):
    return n_list[0] if len(n_list) == 1 else max(n_list[0], max_value(n_list[1:]))