How to exit recursion when condition is met?

user_18556635 0
Viewed 129

I am trying to write a function which prints the minimum number of steps involved to make starting number to target number with multiply by 2 and subtract by 1.

However, I am getting the error:

RecursionError: maximum recursion depth exceeded in comparison

Here's the code I've written:

def no_steps(start,target,sofar):
    if start == target:
        return sofar
    elif start < target and start > 0:
        no_steps(start*2,target,sofar+'*2 ')
        no_steps(start-1,target,sofar+'-1 ')
print(no_steps(2,6,''))

May I know what am I doing wrong and is there any issue with the code?

recursion python
3 Answers

My interpretation is: starting from 2 (start), which sequence of multiplications by 2 and subtractions by 1 will lead to 6 (target) with the least amount of such operations, meaning not exactly always in that order.

On the one side you have a recursion prob (which is what you see in your output) due to missing implementation of correct return statements. On the other, there is also some logic missing to achieve the least amount of computation steps. My combined solution (for the recursion and the minimum num of steps) would be:

def no_steps(start, target, sofar):
    if start == target:
        return sofar
    if 0 < start and 0 < target:
        if (target % 2 == 0) and target > start:
            return no_steps(start, target // 2, '*2 ' + sofar)
        else:
            return no_steps(start, target + 1, '-1 ' + sofar)
    return sofar

no_steps(1, 6, '')
'*2 *2 -1 *2 '

no_steps(2, 6, '')
'*2 -1 *2 '

no_steps(3, 6, '')
'*2 '

no_steps(4, 6, '')
'-1 *2 '

no_steps(5, 6, '')
'-1 -1 *2 '

no_steps(6, 6, '')
''

no_steps(7, 6, '')
'-1 '

no_steps(2, 17, '')
'*2 -1 *2 -1 *2 -1 *2 -1 '

EDIT: fixed the previously flawed logic based on the answer by PabloRuiz.

user_140944600

Don't use recursion for this problem, I came up with a much better solution reversing the problem:

def no_steps(start, target, sofar=''):
    while target != start:
        if target%2 == 0 and target > start:
            target //= 2
            sofar = '*2' + sofar
        else:
            target +=1
            sofar = '-1' + sofar
    print(sofar)
no_steps(2, 17, '')

Note that it assumes that target is bigger than start, if is not just change the order of them to be so.

PD from here a bad answer, but still the first one I posted:

You need to stop the recursion, you can do something like:

def no_steps(start,target, path='', it=0):
    if it < 10 and not reached:
        it+=1
        if start == target:
            print(f'REACHED! in {it} iterations with {path}')
        elif start < 2*target and start > 0:
            no_steps(start*2,target, path=path+'*2', it=it)
            no_steps(start-1,target, path=path+'-2', it=it)
        else:
            print('Start going beyond target')
no_steps(2,6)

You can also add an infamous global variable to stop other branches to continue growing, or just design another algorithm.

user_104160120

You make a common mistake with recursion, i.e you assume that return will collapse all the calls in-between original call and the one that returns something - it won't.

Let's say you run your program for start = 3 and target = 6. no_steps(start*2,target, path=path+'*2', it=it) will return a final result - back to the start = 3 call. And then you ignore this result and call no_steps(start-1,target, path=path+'-2', it=it). Which will in turn call your function with start = 4 and 1 and so forth until infinity (or recursion limit, hence the error). Once you have some result, you need to return it all the way up to the original call.

Another problem in your logic is you want to check all the possible options but have no way of catching an infinite loop like 2->4->3->2->4...

user_92960930
Related