Покрытие рекурсивной функции хвостовой рекурсивной в python

Question

В качестве упражнения я реализовал функцию карты с использованием рекурсии в python следующим образом:

#map function that applies the function f on every element of list l and returns the new list 
def map(l,f):
    if l == []:
        return []
    else:
        return [f(l[0])] + map(l[1:],f)

Мне известно о том, что python не поддерживает оптимизацию хвостовой рекурсии, но как мне написатьта же функция в хвостовой рекурсивной манере?.

Пожалуйста, помогите Спасибо

Answer 1

Хвостовая рекурсия означает, что вы должны непосредственно возвращать результат рекурсивного вызова без каких-либо дополнительных манипуляций.

Очевидная рекурсия в карте состоит в том, чтобы вычислить функцию для одного элемента списка, а затем использовать рекурсивный вызов для обработки остальной части списка. Однако вам необходимо объединить результат обработки одного элемента с результатом обработки остальной части списка, что требует операции после рекурсивного вызова.

Очень распространенный способ избежать этого - переместить комбинацию в рекурсивный вызов; вы передаете обработанный элемент в качестве аргумента и делаете его частью ответственности map также за объединение.

def map(l, f):
    if l == []:
        return []
    else:
        return map(l[1:], f, f(l[0]))

Теперь хвост рекурсивен! Но это тоже явно неправильно. В хвостовом рекурсивном вызове мы передаем 3 аргумента, но map принимает только два аргумента. И затем возникает вопрос о том, что мы делаем с 3-м значением. В базовом случае (когда список пуст), это очевидно: вернуть список, содержащий переданную информацию. В рекурсивном случае мы вычисляем новое значение, и у нас есть этот дополнительный параметр, передаваемый сверху, и у нас есть рекурсивный вызов. Новое значение и дополнительный параметр необходимо свернуть вместе, чтобы передать в рекурсивный вызов, чтобы рекурсивный вызов мог быть хвостовым рекурсивным. Все из которых предлагает следующее:

def map(l, f):
    return map_acc(l, f, [])      

def map_acc(l, f, a):
    if l == []:
        return a
    else:
        b = a + [f(l[0])]
        return map_acc(l[1:], f, b)

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

В приведенном выше примере a называется аккумулятором . Общая идея состоит в том, чтобы переместить операции, которые вы обычно делаете после рекурсивного вызова, в следующий рекурсивный вызов, оборачивая работу, которую внешние вызовы выполнили «до сих пор», и передавая ее в аккумулятор.

Если map можно рассматривать как означающее «вызов f для каждого элемента l и возвращать список результатов», map_acc можно рассматривать как значение «вызов f в каждый элемент l, возвращающий список результатов в сочетании с a, списком уже полученных результатов ".

Answer 2

не совсем ответ, извините, но другой способ реализации карты - написать ее в терминах сгиба.если вы попробуете, вы обнаружите, что это получается только "правильно" с Foldr;использование foldl дает вам обратный список.к сожалению, foldr не является хвостовой рекурсией, в то время как foldl есть.это говорит о том, что в rev_map есть что-то более «естественное» (карта, которая возвращает перевернутый список).к сожалению, я недостаточно образован, чтобы продолжать это (я подозреваю, что вы могли бы обобщить это, чтобы сказать, что нет решения, которое не использует аккумулятор, но я лично не вижу, как аргументировать).

Answer 3

Кажется, что это хвостовая рекурсия:

def map(l,f,x=[]):
    if l == []:
        return x
    else:
        return map(l[1:],f,x+[f(l[0])])

Или в более компактной форме:

def map(l,f,x=[]):
    return l and map(l[1:],f,x+[f(l[0])]) or x

Answer 4

Это будет пример реализации встроенной карты функций в хвостовой рекурсии:

def map(func, ls, res=None):
    if res is None:
        res = []
    if not ls:
        return res
    res.append(func(ls[0]))
    return map(func, ls[1:], res)

Но это не решит проблему отсутствия поддержки Python TRE , что означает, что стек вызовов каждого вызова функции будет удерживаться постоянно.