C++ Recursive Lambda Memory Usage

user_15056025 0
Viewed 66

I got a Wrong Answer at AtCoder, using Recursive Lambda dfs returning void, like this.

  int dfs = y_combinator(
    [&](auto self, int cu, int pa = -1) -> int {
      dp[cu][0] = dp[cu][1] = 1;
      for(auto to: g[cu]){
        if(to != pa){
          self(to, cu);
          dp[cu][0] *= (dp[to][0] + dp[to][1]);
          dp[cu][1] *= dp[to][0];
        }
      }
      // return 0;
    }
  )(0);

Using too much memory (or another point?) seemed to be the reason of WA.

https://atcoder.jp/contests/dp/submissions/31097803

But if I added return value, it resolved.

https://atcoder.jp/contests/dp/submissions/31099529

What happened in this code?

c++
2 Answers

You have specified a trailing return type for your lambda in both cases. Not returning an int makes your program ill-formed. Heed the compiler:

warning: no return statement in function returning non-void [-Wreturn-type]

As well as that, adding y_combinator_result and y_combinator to namespace std is ill-formed (and pointless, as you have using namespace std'd them back into the global namespace)

user_26108100

So what happens here is something I like to call "Compiler black Magic". Something like https://en.wikipedia.org/wiki/Loop_unrolling. Or mayby in your specific cases "Tail Recursion Transformation" or maybe "Tail Recursion Elimination".

Basically Compiler a magic things. They have allot of tricks of the trade to try and help speed up/shrink program binaries.

I put both version of your submersion into the website called godbolt.org see https://godbolt.org/z/69KP5oh8r Without the return statement the compiler just implements the recursive function in a very straight forward manor.

However with the return function in there it does "magic". It does not eliminate the recursive call its still in there but it adds allot of extra code before and after that recursive call.

Compiler's have allot of tricks that can help you're code run faster. However it generally stops helping you if you start doing "ill-formed behavior". In your case its creating a function which your promise will return a int. then when you don't return a int its algorithm's might fail you.

For example if you hade done this.

 y_combinator(
    [&](auto self, int cu, int pa = -1) -> void  {
      dp[cu][0] = dp[cu][1] = 1;
      for(auto to: g[cu]){
        if(to != pa){
          self(to, cu);
          dp[cu][0] *= (dp[to][0] + dp[to][1]);
          dp[cu][1] *= dp[to][0];
        }
      }
    }
  )(0);

You get the same result as retuning zero. Hopefully this was helpful.

user_19435990
Related