V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
AkideLiu
V2EX  ›  程序员

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

  •  
  •   AkideLiu · 2021-05-26 16:07:30 +08:00 · 2130 次点击
    这是一个创建于 1280 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    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,我这么验证哪里存在问题吗

    22 条回复    2021-05-27 19:04:57 +08:00
    wutiantong
        1
    wutiantong  
       2021-05-26 16:24:19 +08:00   ❤️ 1
    答案是 7 么(包括 recur(6)本身)
    AkideLiu
        2
    AkideLiu  
    OP
       2021-05-26 16:28:00 +08:00
    @wutiantong 是的!请问为什么呢?
    wutiantong
        3
    wutiantong  
       2021-05-26 16:32:17 +08:00
    @AkideLiu 你那个解法的代码里 count_x 的计算没尊重 memoisation 呀
    jorneyr
        4
    jorneyr  
       2021-05-26 16:37:35 +08:00
    map_x[0], map_x[1], map_x[2] 先放到 map 里
    hitmanx
        5
    hitmanx  
       2021-05-26 16:50:13 +08:00
    “if memoisation is applied and recur(n-1) is calculated and stored before calculating recur(n-2) and recur(n-3)”

    没太搞懂,如果答案是 7,是不是 recur(0) - recur(6)各计算一次?这样的话得按照从小到大进行计算与储存,即 recur(n-3) => recur(n-2) => recur(n-1)。
    但是题目里写的是先储存 recur(n-1),那岂不是 recur(n-3)和 recur(n-2)的结果会被重复计算?这样答案为何还是 7 ?
    AkideLiu
        6
    AkideLiu  
    OP
       2021-05-26 16:52:21 +08:00
    @wutiantong count_x 在最上面啊,每次 recur function 被 call 都会+1,这个计算方式不适用于 memoisation 吗?
    jorneyr
        7
    jorneyr  
       2021-05-26 16:52:37 +08:00   ❤️ 1
    答案是 7 的话,执行前明显先把 3 的解也存储起来了:
    6 > 5, 4, 3
    5 > 4, 3, 2
    4 > 3, 2, 1
    3 直接查,为 1 次
    4 为 3, 2, 1: 都是直接查,为 3 次
    5 为 4, 3, 2: 因为上面 4 已经存储,也是直接查, 为 3 次

    当然,程序还可以优化为先找相对小的递归的解,这样大的问题就能从小的问题中直接查询答案:
    map_x[n] = recur(n-3) * recur(n-1) * recur(n-1);
    wutiantong
        8
    wutiantong  
       2021-05-26 16:59:40 +08:00   ❤️ 1
    @AkideLiu memoisation 的意义不就是减少原始调用么?所以在你的代码里,当从 map 中返回值时(相当于 memoisation ),就不应该再算作是调用次数了。
    wutiantong
        9
    wutiantong  
       2021-05-26 17:02:39 +08:00
    @hitmanx 那句话是在说 recur(n-1) * recur(n-2) * recur(n-3) 这个表达式中 recur(n-1) 被确保先于后两者求值。在 C++中,同个表达式内的求值顺序通常是不确定的。
    AkideLiu
        10
    AkideLiu  
    OP
       2021-05-26 17:03:06 +08:00
    @wutiantong @jorneyr 太感谢了!恍然大悟!

    这样子输出是 7 !!!

    ```c++

    int count_x = 0;

    unordered_map<int,int> map_x;

    int recur(int n) {
    // cout << n << endl;
    if (map_x.find(n) != map_x.end()) {
    return map_x[n];
    }

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

    }


    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;
    }

    ```
    monkeyNik
        11
    monkeyNik  
       2021-05-26 17:10:27 +08:00
    对本次调用你查表,但你没在内部递归调用前对每个子调用查表,导致你多了一些函数调用。
    至于次数,6 、5 、4 、3 、2 、1 、0,每一个都算一遍并缓存,闭着眼睛也是 7 次。
    lesismal
        12
    lesismal  
       2021-05-26 17:25:52 +08:00
    简单直接的判断方法:
    3 为临界值,n=3 时最多向下 n-1/n-2/n-3,即 recur 最小的参数 n 为 0 ;
    每个 n 对应的值都进行记忆的前提下,每个 n 只需要调用一次 recur ;
    首次调用 recur(6),则整个过程需要对 0-6 挨个计算、记忆,所以是 7 次(不管小于 3 的参数是否记忆,当 n=3/4/5 时 n 也被缓存过、不会被重复调用,所以小于 3 的也不会被重复调用)。
    可以类推首次调用大于等于 3 和小于 3 的次数
    jorneyr
        13
    jorneyr  
       2021-05-26 17:45:44 +08:00
    只要进入 recur 就算一次递归调用吧,不管是查表还是继续递归计算。
    也就是 recur 被调用的次数。
    AkideLiu
        14
    AkideLiu  
    OP
       2021-05-26 17:56:09 +08:00 via iPhone
    @jorneyr 不得不承认,题目确实不严谨。如果结果是 7 的话问题可以问题成 how many times of recur function actually computed 。我的理解是 return memo 就不算是 computed, 而是 cache,但是依然会有 function be called 。
    FACEB00K
        15
    FACEB00K  
       2021-05-26 18:34:37 +08:00   ❤️ 1
    换种写法
    ```cpp
    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 map_x[n];
    }

    int next_1 = (map_x.find(n-1) == map_x.end()) ? recur(n-1) : map_x[n-1];
    int next_2 = (map_x.find(n-2) == map_x.end()) ? recur(n-2) : map_x[n-2];
    int next_3 = (map_x.find(n-3) == map_x.end()) ? recur(n-3) : map_x[n-3];

    map_x[n] = next_1 * next_2 * next_3;
    return map_x[n];
    }
    ```
    LigeLaige
        16
    LigeLaige  
       2021-05-26 20:02:37 +08:00
    顺着 lz 思路,修改如下
    ```cpp
    int recur(int n) {
    if (map_x.find(n) != map_x.end()) {
    return map_x[n];
    }
    count_x++;
    if (n < 3) {
    map_x[n] = 1;
    } else {
    map_x[n] = recur(n-1) * recur(n-2) * recur(n-3);
    }
    return map_x[n];
    }
    ```
    LigeLaige
        17
    LigeLaige  
       2021-05-26 20:03:27 +08:00
    <code>
    int recur(int n) {
    if (map_x.find(n) != map_x.end()) {
    return map_x[n];
    }
    count_x++;
    if (n < 3) {
    map_x[n] = 1;
    } else {
    map_x[n] = recur(n-1) * recur(n-2) * recur(n-3);
    }
    return map_x[n];
    }
    </code>
    hitmanx
        18
    hitmanx  
       2021-05-26 20:12:45 +08:00
    @wutiantong 好吧,谢谢解释。原来是这个意思。
    不过,如果是指这一行内的求值顺序的话,题目为啥要特意强调一下?除非这个顺序对于这个题目的答案(total # of recur() invoked)会有影响,但是基于 memoisation 的话两者应该一样?还是我忽略了啥


    // 1)
    auto n_3 = recur(n-3);
    auto n_2 = recur(n-2);
    auto n_1 = recur(n-1);
    return n_3 + n_2 + n1;

    2)
    auto n_1 = recur(n-1);
    auto n_2 = recur(n-2);
    auto n_3 = recur(n-3);
    return n_1 + n_2 + n3;
    hitmanx
        19
    hitmanx  
       2021-05-26 20:25:27 +08:00
    @AkideLiu 这个取决于你的 cache lookup op 是在 caller side 还是 callee side~

    像 15 楼一样,放在 caller side 的话,就会实质上而不是概念上减少 recur 调用的数量。
    no1xsyzy
        20
    no1xsyzy  
       2021-05-27 09:55:19 +08:00
    @AkideLiu @hitmanx cache lookup 也可能是在 callee wrapper
    比如 Python 可以直接拿 functools.lru_cache() 修饰符,SICP 3.5 也随便地写了一个 memo-proc
    这提倡了一种正交性。
    wutiantong
        21
    wutiantong  
       2021-05-27 10:25:18 +08:00
    @hitmanx 如果有并行求值的情况呢?
    bibitiger
        22
    bibitiger  
       2021-05-27 19:04:57 +08:00
    题目本身不严谨,我觉得应该说明是最少调用次数。
    如果是最少调用次数的话,那应该在 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];
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5462 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 08:06 · PVG 16:06 · LAX 00:06 · JFK 03:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.