итерация Recurssion

Question

так myListToPyList (ЛСТ): принимает LST, объект MyList и возвращает список Python, содержащий те же данные

def myListToPyList(lst): 
    return myListToPyListRec(lst.head) 

вот моя вспомогательная функция:

def myListToPyListRec(node): 
    if node == None: 
     return 
    else: 
     st1 = [] 
     st1.append(node.data) 
     myListToPyListRec(node.next) 
    return st1 

это не работает правильно ,

Теперь вот мой итеративный решение, которое работает правильно:

def myListToPyList(lst): 
    """ 
    Takes a list and returns a python list containing 
    the same data 
    param; lst 
    return; list 
    """ 

    st1 = [] 
    curr = lst.head 
    while curr != None: 
     st1.append(curr.data) 
     curr = curr.next 
    return st1 

Answer 1

Ваш текущий рекурсивный код не работает, потому что каждый раз, когда она вызывается, она создает новый пустой список, добавляет одно значение в список, а затем рекурсивно (без прохождения списка вместе). Это означает, что когда последний элемент в списке ссылок обрабатывается, стек вызовов будет иметь одноуровневые списки Python (N - количество узлов списка).

Вместо этого вы должны создать список только один раз в своей нерекурсивной оболочке. Затем передать его через все рекурсии:

def myListToPyList(lst): 
    result_list = []       # create just one Python list object 
    myListToPyListRec(lst.head, result_list) # pass it to the recursive function 
    return result_list      # return it after it has been filled 

def myListToPyListRec(node, lst): 
    if node is not None    # the base case is to do nothing (tested in reverse) 
     lst.append(node.data)     # if node exists, append its data to lst 
     myListToPyListRec(node.next, lst)  # then recurse on the next node 

Поскольку списки Python изменчивы, нам не нужно ничего возвращать в наших рекурсивных вызовов (None будут возвращены по умолчанию, но мы будем игнорировать это). Список, на который ссылается result_list в myListToPyList, - это тот же объект, на который ссылается lst в каждом из рекурсивных звонков на номер myListToPyListRec. Пока рекурсивная функция мутирует объект на месте (например, с append), а не восстанавливает его, все они видят то же самое.

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

Answer 2

Некоторое время цикла эквивалентно хвостовой рекурсии, и наоборот. (Одна из причин, по которой Python не имеет автоматического устранения хвостового вызова, заключается в том, что часть «наоборот» довольно проста.) Рекурсия хвоста требует, чтобы вы добавили параметр аккумулятора, который будет возвращен в базовом случае. Хотя у меня нет связанного списка для тестирования, я считаю, что следующее должно работать. (Если нет, это близко.) По умолчанию аргументы Python облегчают или не помогают помощнику.

def myListToPyListRec(node, py_list=[]): 
    if node 
     py_list.append(node.data) 
     return myListToPyListRec(node.next, py_list) 
    else: 
     return py_list