Ошибка реализации в рекурсивном выражении Python

Я решаю проблему. Вы должны оставить последний список, но предыдущий список распечатывается снова.

def merge(xs,ys):
  # xs, ys, ss = xs, ys, []
  xs, ys, ss = xs[:], ys[:], []
  while xs!=[] and ys!=[]:
    if xs[0] <= ys[0]:
      ss.append(xs[0])
      xs.remove(xs[0])
    else:
      ss.append(ys[0])
      ys.remove(ys[0])  
  ss.extend(xs)
  ss.extend(ys)
  return ss

accumulator = []
remain = []

def merge2R(xss):

    if len(xss)% 2 != 0 :
     OExcept = len(xss)-1 
     remain.append((xss[OExcept]))
     xss.remove(xss[OExcept])   
     

   
    if xss !=  []:           
     accumulator.append(merge(xss[0],xss[1]))
     xss.remove(xss[0])
     xss.remove(xss[0])   
     return merge2R(xss)

    else: 
     return accumulator + remain

Результат выходит такой. Как я могу это исправить?

>>> merge2R([[2],[1,3],[4,6,7],[5,8],[9]])
[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3], [4, 5, 6, 7, 8], [9]]

Желаемое значение результата:

>>> merge2R([[2],[1,3],[4,6,7],[5,8]])
[[1,2,3], [4,5,6,7,8]]
>>> merge2R([[2],[1,3],[4,6,7],[5,8],[9]])
[[1,2,3], [4,5,6,7,8], [9]]

как определяется merge?

— 31.03.2022 10:30

Я модифицировал!!!

— 31.03.2022 10:41

python recursion

31.03.2022 10:28

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваш код работал, вам просто нужно было сбросить accumulator и remain

def merge2R(xss):
    # Declare use of globals
    global remain
    global accumulator

    if len(xss) % 2 != 0:
        OExcept = len(xss)-1
        remain.append((xss[OExcept]))
        xss.remove(xss[OExcept])

    if xss != []:
        accumulator.append(merge(xss[0], xss[1]))
        xss.remove(xss[0])
        xss.remove(xss[0])
        return merge2R(xss)

    else:
        x = accumulator + remain
        # Must reset accumulator and remain
        accumulator = []
        remain = []
        return x

Поскольку вы инициализируете оба массива пустыми, добавьте к ним:

# Remain
remain.append((xss[OExcept])) 
# Accumulator
accumulator.append(merge(xss[0], xss[1]))

После того, как вы закончите с данными в этих массивах (в конце функции), вам нужно их отбросить:

accumulator = []
remain = []

Результат отказа от отбрасывания этих массивов очевиден при многократном вызове функции с одним и тем же аргументом:

print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))

[[1, 2, 3]]
[[1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

Можно ли сказать, что этот код рекурсивен?

— 31.03.2022 10:53

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

— 31.03.2022 10:55

Почему вы сбрасываете аккумулятор и основной в конце?

— 31.03.2022 11:25

я добавлю это к моему ответу

— 31.03.2022 11:45

31.03.2022 10:49