Python使用递归求列表最大值的三种方法

Python使用递归求列表最大值的三种方法 方法1（非递归）

def max_value1(S):
    if len(S) == 0:
        return
    result = S[0]
    for i in S:
        if result < i:
            result = i
    return result

方法2

def max_value2(arr, max, low, high):
    """
    使用递归求最大值
    """
    if len(arr) == 0:
        return

    if low >= high:
        return max
    else:
        if max < arr[low]:
            max = arr[low]
        low += 1
        return max_value2(arr, max, low, high)

方法3

def max_value3(arr):
    """
    使用递归求最大值
    """
    def inner_max(arr, max, low, high):
        if len(arr) == 0:
            return

        if low >= high:
            return max
        else:
            if max < arr[low]:
                max = arr[low]
            low += 1
            return inner_max(arr, max, low, high)
    return inner_max(arr, arr[0], 0, len(arr))

方法4

def max_value4(arr):
    """
    使用递归求最大值
    """
    # 特殊情况
    arr_length = len(arr)
    if arr_length == 0:
        return
    if arr_length == 1:
        return arr[0]
    if arr_length == 2:
        max = arr[0] if arr[0] > arr[1] else arr[1]
        return max

    # 拆成两部分，一个往前比较，一个往后比较
    def inner_max(arr, left_max, right_max, left_index, right_index, low, high):
        if left_index == low and right_index == high:  # 比完了
            max = left_max if left_max > right_max else right_max
            return max
        else:
            # 左边最大值
            left_max = left_max if left_max > arr[left_index] else arr[left_index]
            left_index -= 1

            # 右边最大值
            right_max = right_max if right_max > arr[right_index] else arr[right_index]
            right_index += 1

            # 递归比较
            return inner_max(arr, left_max, right_max, left_index, right_index, low, high)

    # 求中间的数
    mid = None
    mid_index = len(arr)//2
    if len(arr) % 2 == 0:
        mid1 = arr[mid_index]
        mid2 = arr[mid_index-1]
        mid = mid1 if mid1 > mid2 else mid2
    else:
        mid = arr[mid_index]

    # 一个从中间往前比较，一个从中间往后比较，比完以后再比较
    return inner_max(arr, mid, mid, mid_index-1, mid_index+1, 0, len(arr))

完整代码

# 使用递归找最大值
def max_value1(S):
    if len(S) == 0:
        return
    result = S[0]
    for i in S:
        if result < i:
            result = i
    return result


def max_value2(arr, max, low, high):
    """
    使用递归求最大值
    """
    if len(arr) == 0:
        return

    if low >= high:
        return max
    else:
        if max < arr[low]:
            max = arr[low]
        low += 1
        return max_value2(arr, max, low, high)


def max_value3(arr):
    """
    使用递归求最大值
    """
    def inner_max(arr, max, low, high):
        if len(arr) == 0:
            return

        if low >= high:
            return max
        else:
            if max < arr[low]:
                max = arr[low]
            low += 1
            return inner_max(arr, max, low, high)
    return inner_max(arr, arr[0], 0, len(arr))


def max_value4(arr):
    """
    使用递归求最大值
    """
    # 特殊情况
    arr_length = len(arr)
    if arr_length == 0:
        return
    if arr_length == 1:
        return arr[0]
    if arr_length == 2:
        max = arr[0] if arr[0] > arr[1] else arr[1]
        return max

    # 拆成两部分，一个往前比较，一个往后比较
    def inner_max(arr, left_max, right_max, left_index, right_index, low, high):
        if left_index == low and right_index == high:  # 比完了
            max = left_max if left_max > right_max else right_max
            return max
        else:
            # 左边最大值
            left_max = left_max if left_max > arr[left_index] else arr[left_index]
            left_index -= 1

            # 右边最大值
            right_max = right_max if right_max > arr[right_index] else arr[right_index]
            right_index += 1

            # 递归比较
            return inner_max(arr, left_max, right_max, left_index, right_index, low, high)

    # 求中间的数
    mid = None
    mid_index = len(arr)//2
    if len(arr) % 2 == 0:
        mid1 = arr[mid_index]
        mid2 = arr[mid_index-1]
        mid = mid1 if mid1 > mid2 else mid2
    else:
        mid = arr[mid_index]

    # 一个从中间往前比较，一个从中间往后比较，比完以后再比较
    return inner_max(arr, mid, mid, mid_index-1, mid_index+1, 0, len(arr))


if __name__ == "__main__":
    import time
    import sys
    sys.setrecursionlimit(10000) # 设置最大递归深度
    
    arr = list(range(1000))
    start_time = time.time()
    print(max_value1(arr))
    end_time = time.time()
    print(end_time - start_time)
    print("===================================")
    
    start_time = time.time()
    print(max_value3(arr))
    end_time = time.time()
    print(end_time - start_time)
    print("===================================")

    start_time = time.time()
    print(max_value4(arr))
    end_time = time.time()
    print(end_time - start_time)
    print("===================================")