C++ 关于 recursion 的一个小问题

[AkideLiu]

题目：

Consider the following recursive function:

int recur(int n) {
  if (n < 3)
    return 1;
  return recur(n-1) * recur(n-2) * recur(n-3);
}

if memoisation is applied and recur(n-1) is calculated and stored before calculating recur(n-2) and recur(n-3), for the call recur(6), how many calls will be made to recur()?

我的解法这样的：

int count_x = 0;

unordered_map<int,int> map_x;

int recur(int n) {
    count_x++;
    if (n < 3)
        return 1;

    // cout << n << endl;
    if (map_x.find(n) != map_x.end()) {
        return map_x[n];
    }
    map_x[n] = recur(n-1) * recur(n-2) * recur(n-3);
    return map_x[n];
}


TEST(test, recur) {
    cout << recur(6) << endl;
    cout << count_x << endl;
}

输出结果是：

1
13

现在明确题目的答案不是 13，我这么验证哪里存在问题吗

[wutiantong]

@hitmanx 如果有并行求值的情况呢？

[bibitiger]

题目本身不严谨，我觉得应该说明是最少调用次数。
如果是最少调用次数的话，那应该在 caller 的时候对 recur(n-1)，recur(n-2)，recur(n-3)也进行查表，这样就不会进入 recur()。
而要得出 f(n-1),必然会得到 f(n-2),f(n-3)...f(n-n), 所以 f(n)对于 f()的调用必然等于 n+1 。

int count_x = 0;

unordered_map<int,int> map_x;

int recur(int n) {
count_x++;

if (map_x.find(n) != map_x.end()) {
return map_x[n];
}

if (n < 3){
map_x[n] = 1;
return 1;
}


int temp_n1 = map_x.find(n-1) == map_x.end()?recur(n-1) :map_x[n-1];
int temp_n2 = map_x.find(n-2) == map_x.end()?recur(n-2) :map_x[n-2];
int temp_n3 = map_x.find(n-3) == map_x.end()?recur(n-3) :map_x[n-3];

map_x[n] = temp_n1*temp_n2*temp_n3;

return map_x[n];
}