python - 坚持递归

Question

我正在尝试编写一个带有 2 个参数的函数，一个 int 和一个列表。我必须将列表中的每个元素与 int 进行比较，并将它们存储在由 2 个列表组成的元组中，一个数字大于的列表和一个数字小于的列表。我正在尝试递归地执行此操作，但我不知道如何存储这些值，以便在我使用递归时它们不会被删除。

def greater_less(v:int,l:list):
    if l == []:
       return ([],[]) 
    elif l[0] > v:
       more = [l[0]] 
       return more + greater_less(v,l[1:])
    elif l[0] < v:
       less = [l[0]]
       return less + greater_less(v,l[1:]) 

问题是...当 l == [] 时，一切都被清除了。此外，当我递归调用我的函数时，我相信之前的所有内容也都被清除了

练习递归，所以提示如何用递归解决我的问题会很棒

Answer 1

让我们写一些代码:

def greater_less(v, l):
    # First, are we in the base case?
    if not l:
        return [], []

    # Second, do the recursive step
    smaller, greater = greater_less(v, l[1:])

    # Now, we also have l[0] to insert into these lists.
    if l[0] < v:
        smaller.insert(0, l[0])
    elif l[0] > v:
        greater.insert(0, l[0])
    else:
        pass

    # Finally, return these lists
    return smaller, greater

请注意，我们存储从递归调用返回的列表，添加到正确的列表，然后返回它们。

---

让我们看一下这段代码的运行。为了减少重复，我将标记函数 A 到 D 中的 4 段代码。所以 A 将是基本情况检查 ( if not l... ) 而 C 将是 if l[0] < v ... else: pass代码。

main() calls greater_less(2, [1,2,3])
     A: We are not in the base case because l has 3 elements.
     B: Recursive call of greater_less(2, [2, 3])
         A: We are not in the base case because l has 2 elements.
         B: Recursive call of greater_less(2, [3])
              A: We are not in the base case because l has 1 element.
              B: Recursive call of greater_less(2, [])
                  A: We __are__ in the base case because l has 0 elements.
                     Therefore, we won't reach B, C, or D of this call.
                     We return [], [].
              B: Recursive call returns. We have smaller = [], greater = []
              C: l[0] is 3 which is greater than 2.
                 Therefore, we prepend onto greater.
              D: Return smaller = [], greater = [3]
         B: Caller returns. We have smaller = [], greater = [3]
         C: l[0] is 2, which is equal to 2.
            So we don't prepend this number to either list.
         D: return smaller = [], greater = [3]
     B: Caller returns. We have smaller = [], greater = [3]
     C: l[0] is 1, which is less than 2.
        So prepend to the smaller list.
     D: Return smaller = [1], greater = [3]
main's call to greater_less() now returns with ([1], [3])