2

我正在为我的数据结构课程学习递归的第一阶段，我们的教授告诉我们，我们应该能够采用递归方法并能够提出问题大小以及递归方程。当问题大小取决于一个为简单起见假定为正的变量 N 时，我可以编写一个递归方程，例如：只要在第一次调用时 n > 0，此方法就会简单地打印输入数字。

public static int simpleCounter(int N) {
    if (n == 0) {
        return;
    }
    else {
        return 1 + simpleCounter(N - 1);
    }
 }

但是，当问题规模更复杂时，例如取决于 2 个变量，我无法创建递归方程，因为我不知道如何处理变量。此方法计算 2 个数字可以相减多少次，假设第一次调用时 count 始终为零，并且 a 和 b 都是正数。

public static int complexCount(int a, int b, int count) {
    if ((a - b) <= 0) { 
        return 0; 
    }
    else {
      count = 1 + complexCount((a - b), b, count + 1)
      return count;
     }
 }

那么这里的问题大小是多少？它与a和b都无关吗？在不知道问题大小的情况下，我无法得出递归方程：基数：T(0) = 1 递归：T(N) = 1 + ??

4

1 回答 1

0

递归关系并不总是必须涉及单个变量，事实上，具有多个变量的递归关系是很常见的。在这里，递归关系将是

T(a, b) = 1 + T(a - b, b)（如果 a ≥ b）

T(a, b) = 1（否则）

然后，您可以根据 a 和 b 解决此递归关系，以得出最终解决方案。

希望这可以帮助！

于 2013-11-05T00:56:55.020 回答