converting iterative code to recursive code python3

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

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top