如何在满足条件时退出递归？

Question

我正在尝试编写一个函数，该函数打印将起始数字乘以 2 并减去 1 所需的最少步数。

但是，我收到错误消息：

RecursionError: maximum recursion depth exceeded in comparison

这是我编写的代码：

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,''))

我可以知道我做错了什么吗？代码有什么问题吗？

Answer 1

我的解释是：从2（start）开始，乘以2减1的顺序会得到6（target），这样的操作次数最少，意思是并不总是按照这个顺序。

一方面，由于缺少正确的 return 语句的实现，您有一个递归概率（这是您在输出中看到的）。另一方面，也缺少一些逻辑来实现最少的计算步骤。我的组合解决方案（对于递归和最少步骤数）是：

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 '

编辑：根据 PabloRuiz 的回答修复了之前有缺陷的逻辑。

Answer 2

不要使用递归解决这个问题，我想出了一个更好的解决方案来解决这个问题：

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, '')

请注意，它假设目标大于开始，如果不只是改变它们的顺序。

PD 这里是一个错误的答案，但仍然是我发布的第一个：

你需要停止递归，你可以这样做：

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)

你也可以添加一个臭名昭著的全局变量来阻止其他分支继续增长，或者只是设计另一种算法。

Answer 3

你在递归时犯了一个常见的错误，即你假设 return 会折叠所有调用 in-between 原始调用和 return 的调用 - 它不会.

假设您运行开始 = 3 和目标 = 6 的程序。no_steps(start*2,target, path=path+'*2', it=it) 将 return 最终结果 - 返回到开始 = 3 调用。然后你忽略这个结果并调用 no_steps(start-1,target, path=path+'-2', it=it)。这将依次使用 start = 4 和 1 调用您的函数，依此类推直到无穷大（或递归限制，因此出现错误）。获得一些结果后，您需要 return 一直到原始调用。

您的逻辑中的另一个问题是您想要检查所有可能的选项，但无法捕获无限循环，如 2->4->3->2->4...

如何在满足条件时退出递归？

How to exit recursion when condition is met?

python

recursion