python minmax仅使用递归 [英] python minmax using only recursion

问题描述

我正在尝试构建一个接受列表并返回(min，max)元组的函数.

I am trying to build a function that takes in a list and returns a tuple of (min, max).

例如

[2,1,4,9,4.5]

会返回

(1, 9)

我正在尝试仅使用递归，并且想要执行此任务而不使用其他使事情变得非常简单的事情(例如min()，max()，sort()，sorted()，loop..etc)

I am trying to use only recursion and want to perform this task without using other things that would make this very easy (such as min(),max(),sort(),sorted(),loop..etc)

到目前为止，我已经能够创建找到最大值的函数

So far, I have been able to create function that find maximum

def findmax(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]])
    elif alist[0] <= alist[1]:
        return findmax([alist[1]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]] + alist[2:])
    elif alist[0] <= alist[1]:
        return findmax(alist[1:])

其中

findmax([2,1,4,9,4.5])

返回

(9,)

和找到最小值的函数(两者没有太大区别)

and a function that find minimum (which is not too different)

def findmin(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmin([alist[1]])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmin(alist[1:])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]] + alist[2:])

其中

findmin([2,1,4,9,4.5])

返回

(1,)

是否有一种方法可以仅使用递归将这两个单独的函数放到一个函数中，以便返回期望的

Is there a way to put this two separate functions into one using only recursion so that it would return a desired result of

(1, 9)

我们将不胜感激.

推荐答案

分别查找max或min很容易.困难的是通过递归调用找到最大值和最小值. 尾部递归正是为此目的(通过递归调用来维护和更新变量的状态)，通常易于编写:

To find either max or min separately is easy. What is difficult is to find both max and min through recursive calls. Tail recursion is exactly for this (maintain and update status of variables through recursive calls) and is usually straightforward to write:

def findminmax(L):
    def inner(L1, min, max):
        if L1 == []:
            return (min, max)
        elif L1[0] > max:
            return inner(L1[1:], min, L1[0])
        elif L1[0] < min:
            return inner(L1[1:], L1[0], max)
        else:
            return inner(L1[1:], min, max)
    return inner(L[1:], L[0], L[0])

findminmax([2,1,4,9,4.5])
# => (1, 9)

无需分配和花式列表索引.仅需要最基本的列表操作.递归结构清晰且非常标准(显然请参见基本案例，约简和函数递归调用)，并且该代码也像普通英语一样易读.

No need for assignment and fancy list indexing. Only the most basic list operation is needed. The recursion structure is clear and very standard (obviously see base case, reduction and function recursive call) and the code is also very readable as plain English.

更新

进行一些修改以处理字符串输入和空列表或字符串输入:

A little modification to handle the string input and empty list or string input:

def findminmax(LS):
    def inner(LS1, min, max):
        if not LS1:
            return (min, max)
        elif LS1[0] > max:
            return inner(LS1[1:], min, LS1[0])
        elif LS1[0] < min:
            return inner(LS1[1:], LS1[0], max)
        else:
            return inner(LS1[1:], min, max)
    try:
        return inner(LS[1:], LS[0], LS[0])
    except IndexError:
        print("Oops! That was no valid input. Try again...")

findminmax([2,1,4,9,4.5])
# => (1, 9)

findminmax([2])
# => (2, 2)

findminmax('txwwadga')
# => ('a', 'x')

findminmax('t')
# => ('t', 't')

findminmax([]) # empty list
# => Oops! That was no valid input. Try again...

findminmax('') # empty string
# => Oops! That was no valid input. Try again...

这篇关于python minmax仅使用递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！