c - 将 X 转换为 Y 的步骤数。(整数)

Question

所以我对这个递归函数的工作原理感到困惑。我不明白这实际上是如何产生答案的。问题指出:

写一个返回最少步数的递归函数 需要将 X 转换为 Y。如果 X > Y，返回 1000000000，表示不存在解。(例如，如果 X = 13 且 Y = 28，则正确的响应将是 2 - 首先您将 1 添加到 13 以获得14，然后 14 乘以 2 得到 28。)随意调用提供的函数

这是解决方案:

int min(int x, int y) {
    if (x < y) return x;
    return y;
}

// Returns the minimum number of steps to transform x into y, or
// 100000000 to indicate no solution.
int minSteps(int x, int y) {
    if (x > y) return NO_SOLUTION; 
    if (x == y) return 0; 
    int mult = 1 + minSteps(2*x, y);
    int add = 1 + minSteps(x+1, y); 
    return min(add, mult); 
}

如果有人能解释一下解决方案，那就太好了。谢谢!

Answer 1

许多可以用递归解决的问题的核心在于将原始问题简化为较小的问题并继续该过程直到它缩小为已知问题的原则。

这个问题非常适合这种方法。 您的答案是将 x 转换为 y 的一系列算术运算。即，像这样:

x ? a ? b ? c ? ... ? y

? 表示乘以 2 或加 1；和 a,b,c... 表示对先前结果应用操作后的中间结果。例如，5 到 22 的转换可以这样描述:

5 (*2) 10 (+1) 11 (*2) 22

现在让我们回到归约原则。从给定的 x 开始，我们需要选择第一步。它可以是 *2 OR^[1] +1，我们还不知道，所以我们需要同时检查它们。在 *2 的情况下，x 转换为 2x，在 +1 的情况下，x 转换为 x+1。瞧，我们前进了一步，减少了问题!现在我们有 2 个较小的问题要解决 - 一个用于 2x，一个用于 x+1，然后找到结果之间的最小值。由于我们正在计算步数，因此我们创建了 2 个不同的计数器(一个用于所采取的每种类型的操作)并将 1 添加到每个计数器(因为我们执行了一个步骤已经)。为了完成每个计数器的实际值的计算，我们需要解决两个较小的问题——为了解决它们，我们用新的输入递归调用函数(两次，每个输入一次)。算法以这种方式继续，每次都减少问题，直到到达停止条件，它可以是 x == y(这是一个有效的转换)或 x > y (无效转换)。在 x == y 的情况下，恰好需要 0 个步骤，执行停止，导致调用堆栈回退，填充发起的计数器的实际值递归分支。在 x > y 的情况下，结果是 1000000000(假定它太大而不是实际结果，因此总和将被丢弃，因为总和大于来自第二个分支)。通过使用递归树进行可视化通常可以更好地理解此过程(例如，请参阅@DavidBowling 的回答。错误，由于某种原因被删除...)。

^[1] 虽然在这个问题中很清楚，但有时操作之间的区别可能很模糊。将问题分解为多个较小的问题非常重要，它们之间没有任何重叠。