整体解决方案(递归函数)

Question

我有这个递归函数，它是搜索爬楼梯问题的可能解决方案。 是否可以在没有全局变量的情况下返回最终计数？

def foo(number, steps):
global count
if steps == number:
count += 1
else:
if number - 2 >= steps:
foo(number, steps+2)
if number -1 >= steps:
foo(number, steps+1)
return count

Answer 1

通常，这些递归算法的思想是在当前调用中使用递归调用的返回值。

在这种特殊情况下：从当前位置到达顶部的方法数量是从一步开始的方式和以双步开始的方式的总和。

我们还可以通过为我们超出目标的情况添加额外的基本情况来简化逻辑，并报告在这种情况下没有解决方案。这意味着我们不需要在每次递归调用之前进行单独的检查，并且它还处理要求我们从目标之外开始的情况。

最后，我们不需要单独跟踪所走的步数和到目标的总距离：我们关心的只是剩余的距离。

所以：

def number_of_paths(distance):
if distance < 0:
# We overstepped the goal, so now we can't get there.
return 0
elif distance == 0:
# We're there, so there's exactly one way to get there: wait in place.
return 1
else:
# We try both possible step sizes and total the results.
return number_of_paths(distance - 2) + number_of_paths(distance - 1)