Блог

Я начинающий программист, и в последнее время я изучаю функции рекурсии в Python3. Я работаю над кодом, который в основном обеспечивает минимальные шаги, необходимые для того, чтобы число N стало M, проходящим процессы добавления 1, деления 2 или кратного 10. Я выполнил итеративную функцию, которая работает хорошо, но как начинающий студент рекурсивных функций, я хочу иметь возможность преобразовать код в рекурсивный код, и в этом коде я не добился успеха.

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

ИТЕРАТИВНЫЙ КОД

 def scape(N, M, steps=0):
    if N == M:
        return 0

    currentoptions = [N]

    while True:
        if M in currentoptions:
            break

        thisround = currentoptions[:]
        currentoptions = []

        for i in thisround:
            if (i%2) == 0:
                currentoptions.append(i // 2)
            currentoptions.append(i   1)
            currentoptions.append(i * 10)

        steps  = 1

    return steps
  

ПРИМЕР

 print(scape(8,1))
  

ВЫВОД -> 3
Потому что 8/2 -> 4/2 -> 2/2 = 1

Здесь сложно использовать чистую рекурсию (без передачи вспомогательных структур данных). Вы могли бы выполнить sth в следующих строках:

 def scape(opts, M, steps=0):
    if M in opts:
        return steps
    opts_ = []
    for N in opts:
        if not N%2:
            opts_.append(N // 2)
        opts_.extend((N   1, N * 10))
    return scape(opts_, M, steps 1)

>>> scape([8], 1)
3
  

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

 def scape(N, M):
    steps = 0
    def helper(opts):
        nonlocal steps
        if M in opts:
            return steps
        opts_ = []
        for N in opts:
            if not N%2:
                opts_.append(N // 2)
            opts_.extend((N   1, N * 10))
        steps  = 1
        return helper(opts_)
    return helper([N])

>>> scape(8, 1)
3