Converting Iterative Code to Recursive Code Python3

Question

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

user2390182 · Accepted Answer · 2020-10-28 15:56:57Z

1

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

answered Oct 28, 2020 at 15:56

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Inovaula Over a year ago

Thank you! I changed some structures to fit my goals and I could reach it.

Collectives™ on Stack Overflow

Converting Iterative Code to Recursive Code Python3

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related