Converting Iterative Code to Recursive Code Python3

user_13931233 0
Viewed 57

I'm a beginner programming student and I've been studying recursion functions in Python3 lately. I'm working on a code that basically provides minimum steps requires for a number N to be M undergoing processes of adding 1, divide 2, or multiple 10. I did an iterative function that works well, but as a beginner student of recursive functions I want to be able to convert the code to a recursive code and in this code I was not successful.

I've been reading about this process lately, but as I said it was a very hard implementation for my skills. I know if I want to convert an iterative code I need to use the main loop condition as my base case and the body of the loop as the recursive step and that is all I know.
I would really appreciate it if you could help me to find the base case and the recursive steps of this code. I don't want you to write my code, I want you to help me in reaching my goals.

ITERATIVE CODE

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

EXAMPLE

print(scape(8,1))

OUTPUT -> 3 Because 8/2 -> 4/2 -> 2/2 = 1

recursion iteration python-3.x
1 Answers

It is difficult to use pure recursion here (without passing around auxiliary data structures). YOu could do sth along the following lines:

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

Or in order to keep the signature (and not pass around redundant arguments), you could use a recursive helper function:

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
user_23901820
Related