Как рекурсивная функция возвращает кортеж списков?

Question

Вопрос: Определить рекурсивную функцию с именем раздельный; он передается предикатом и списком; он возвращает 2-кортеж, индекс 0 которого представляет собой список всех значений в списке аргументов, для которых предикат возвращает True, и индекс 1 которого является списком всех значений в списке аргументов, для которых предикат возвращает False. Вызов separate(predicate.is_positive,[1,-3,-2,4,0,-1,8]) возвращает ([1,4,8], [-3,-2,0,-1]). Примечание 0 не является положительным. Подсказка: как быстрая версия функции питания в заметках, вы можете определить и привязать (но не перекрутить) локальное имя или написать вложенную функцию (например, квадрат в силе), чтобы помочь в вычислении.

Вот пример его степенной функции:

def power(a,n): 
    def square(n) : n*n 
    if n == 0: 
     return 1 
    else: 
     if n%2 == 1: 
      return a*power(a,n-1) 
     else: 
      return square(power(a,n//2)) 

Моя попытка:

def separate(p,l): 
    l1=[] 
    l2=[] 
    if l == []: 
     return [],[] 
    else: 
     if p(l[0]): 
      l1=([l[0]]+map_pos(p,l[1:])) 
      return l1,l2 
     else: 
      l2.extend([l[0]]+separate(p,l[1:])) 
      return l1,l2 

вызова этой функции: print(predicate.is_positive,[1, -3, -2, 4, 0, -1, 8]) воля дает мне: TypeError: can only concatenate list (not "tuple") to list

Примечание predicate.is_positive является функцией из предикатного модуля, которая принимает int и возвращает True, если int i положительный.

Может кто-нибудь, пожалуйста, помогите мне с этим? С фактическим кодом будет приятно по достоинству оценить.

Answer 1

Это может быть whay вы пытаетесь сделать

def separate(p, L): 
    if L == []: 
     return [], [] 

    l1, l2 = separate(p, L[1:]) 

    item = L[0] 

    if p(item): 
     l1.append(item) 
    else: 
     l2.append(item) 
    return l1, l2  

Это не очень эффективно из-за L[1:], который создает новый список для каждого элемента

вы можете использовать аргумент по умолчанию, чтобы избежать получения ломтики

def separate(p, L, idx=0): 
    if idx == len(L): 
     return [], [] 

    l1, l2 = separate(p, L, idx + 1) 

    item = L[idx] 

    if p(item): 
     l1.append(item) 
    else: 
     l2.append(item) 
    return l1, l2  

Он по-прежнему выглядит неуклюжим. Это не задача, которая требует рекурсивного решения.