C++ 理解递归函数

Question

我需要一些帮助来理解这个递归函数。它在 n = 5 时返回 101 但我不明白为什么。这是函数:

string RecursiveMystery(int n) {
  string s = "1";
  if (n % 2 == 0) {
    s = "0";
  }
  if (n < 2) {
    return s;
  }
  return RecursiveMystery(n / 2) + s;

所以当RecursiveMystery(5)时，应该进入结束返回函数RecursiveMystery(5/2) 等于0 + 1 即 01(因为在 RecursiveMystery(5)< 时 s = 1/)。我无法理解它是如何返回 101 的。

Answer 1

如果您调用 RecursiveMystery(5)，它会返回 RecursiveMystery(2) + "1"。所以我们必须评估 RecursiveMystery(2)，它返回 RecursiveMystery(1) + "0"。 RecursiveMystery(1) 返回“1”。

因此

RecursiveMystery(5) = RecursiveMystery(2) + "1"= RecursiveMystery(1) + "0"+ "1"= "1"+ "0"+ "1"= "101"

关于 RecursiveMystery 方法的更多信息。它计算数字 n 的二进制表示。如果 n 是奇数，它在最后写一个 1，如果 n 是偶数，它在最后写一个 0 .而 n/2 只是数字 n 没有最后一位(二进制表示)。