Как создать рекурсивную функцию для создания списка значений

Question

Привет, я пытаюсь понять, как работает рекурсия. Я знаю, что рекурсия вызывает себя неоднократно. Мне любопытно узнать, можно ли использовать рекурсию для решения простых задач, таких как создание списка от 0 до 9. Вот программа, которую я пытаюсь преобразовать в рекурсию:

Для версии l oop

def create_list(start, count):
    mylist = []
    for i in range(start, start + count):
        mylist.append(i)
    return mylist


the_list = create_list(0, 8)

print(the_list)

Неработающая рекурсивная версия

def create_list(start, count):
    mylist = []
    mylist = create_list_recurse(start, start + count)
    return mylist


def create_list_recurse(start, end):
    if start >= end:
        return

    create_list_recurse(start + 1, end)

print(create_list(0, 9))

Я застрял, заставляя рекурсивную версию работать. Программа просто вернет список значений. Скажите, пожалуйста, неправильно ли я решил эту проблему?

Answer 1

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

def create_list(start, length):
    if length:
        return [start]+create_list(start+1, length-1)
    else:
        return []

print (create_list(0,8))

Answer 2

Mark и RufusVS очень хорошо объяснили, но если вы хотите понять это с помощью своего кода, поскольку вы спросили, что вы сделали не так. Вот он:

def create_list(start, count):
    mylist = []
    mylist = create_list_recurse(start, start + count)
    return mylist


def create_list_recurse(start, end):
    #print(start, end)
    if start < end:
        return [start] + create_list_recurse(start + 1, end)
    elif start==end:
        return [start]

print(create_list(0, 9))

Answer 3

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

Часто бывает полезно сначала подумать о граничном случае, а затем подумать о том, что происходит с одним рекурсивным вызовом.

Вам также нужно не забыть вернуться из вашей функции (и подумать о том, что должно возвращать краевое условие (например, пустой список):

def create_list_recurse(start, end):
    if start > end:
        return []

    return [start] + create_list_recurse(start + 1, end)

create_list_recurse(0, 9)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

create_list_recurse(3, 1) #edge case returns empty 
# []