Can you capture a reference in a recursive lambda?

Question

I've fully solved a particular problem on HackerRank (https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem) using a recursive solution with memoization:

std::map<int, int> memoize;

int davis_staircase(int n) {
    if (n == 0) {
        return 1;
    } else if (n < 0) {
        return 0;
    }

    auto find = memoize.find(n);
    if (find != memoize.end()) {
        return find->second;
    }

    int num_steps = davis_staircase(n - 1) + davis_staircase(n - 2) + davis_staircase(n - 3);
    memoize[n] = num_steps;

    return num_steps;
}

I would like to hide the global std::map (without using a class) that I'm using as the lookup and thought I'd try creating a lambda that I can call recursively and also capture the cache/map by reference. I've tried the following:

int davis_staircase_2(int n) {

    std::map<int, int> memo;

    //auto recurse = [&memo](int n) -> int {                    // attempt (1)
    //std::function<int(int)> recurse = [&memo](int n) -> int { // attempt (2)
    std::function<int(std::map<int, int>&, int)> recurse = [](std::map<int, int>& memo, int n) -> int { // attempt (3)
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            return 0;
        }

        auto find = memo.find(n);
        if (find != memo.end()) {
            return find->second;
        }

        //int num_steps = recurse(n - 1) + recurse(n - 2) + recurse(n - 3); // attempt (1) or (2)
        int num_steps = recurse(memo, n - 1) + recurse(memo, n - 2) + recurse(memo, n - 3); // attempt (3)

        memo[n] = num_steps;

        return num_steps;
    };

    //return recurse(n); // attempt (1) or (2)
    return recurse(memo, n); // attempt (3)
}

I have 3 slightly different attempts interleaved above but I cannot get any to compile. Is what I'm trying to do, possible?

I'm using clang on MacOS:

Apple LLVM version 10.0.0 (clang-1000.10.44.4)
Target: x86_64-apple-darwin18.2.0
Thread model: posix

`std::function&, int)> recurse = [](std::map& memo, int n) -> int {` -> `auto recurse = [&memo, &recurse](std::map& memo, int n) -> int {`. — George, Apr 25 '19 at 14:03
[This post](https://stackoverflow.com/questions/14531993/can-lambda-functions-be-recursive/14532044) would be helpful. — Hiroki, Apr 25 '19 at 14:13
offtopic: this can be solved without recursion, by representing problem as a matrix and use of exponentiation by squaring. This way you will change problem from `o(n)` complexity to `o(log(n))` complexity. On other hand since constraints for `n` are so small `<36` it will be an overkill. — Marek R, Apr 25 '19 at 14:42

Jarod42 · Accepted Answer · 2019-04-25T14:18:25.147

You forget to capture recurse, so your code might be

std::function<int(int)> recurse = [&recurse, &memo](int n) -> int { // attempt (2)

or

std::function<int(int)> recurse = [&](int n) -> int { // attempt (2)

In the same way, for // attempt (3):

std::function<int(std::map<int, int>&, int)> recurse = [&recurse](std::map<int, int>& memo, int n) -> int { // attempt (3)

// attempt (1) cannot be fixed as is, as type of recurse is used before it is defined.

To do it without std::function, you might use Y-combinator (require C++14, for generic lambda):

int davis_staircase_2(int n) {
    std::map<int, int> memo;
    auto recurse = [&memo](auto self, int n) -> int { // attempt (4)
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            return 0;
        }

        auto find = memo.find(n);
        if (find != memo.end()) {
            return find->second;
        }

        int num_steps = self(self, n - 1) + self(self, n - 2) + self(self, n - 3); // attempt (4)

        memo[n] = num_steps;

        return num_steps;
    };
    return recurse(recurse, n); // attempt (4)
}

score 0 · Answer 2 · answered Apr 25 '19 at 14:17

0

You don't need a recursive function ...

int stepPerms(int n) {

  std::map<int, int> memoize;

  memoize[-2] = 0;
  memoize[-1] = 0;
  memoize[0] = 1;

 for(int i=1;i<=n;++i)
 {
   memoize[i] = memoize[i - 1] + memoize[i - 2] + memoize[i-3];
 }

 return memoize[n];
}

answered Apr 25 '19 at 14:17

cprogrammer

5,503
3
36
56

2

No need of `map` neither, a vector, or even, a circular buffer would be enough. – Jarod42 Apr 25 '19 at 14:20
True. But it will make the code a bit hard to read and anyway ... I just wanted to point the ideea, not write the perfect code :) – cprogrammer Apr 25 '19 at 14:24
cprogrammer: Thanks for that solution mate. I'd be interested to know the thought process applied to arrive at something like that. And, also with the use of a circular buffer @Jarod42 – yorztif Apr 25 '19 at 14:40
1

@yorztif: [Demo with circular buffer](http://coliru.stacked-crooked.com/a/fe738468f5e614fa) – Jarod42 Apr 25 '19 at 15:11

score 0 · Answer 3 · answered Apr 25 '19 at 14:21

You can do recursive lambda without type erasure (std::function). This is how it's done with generic lambdas:

auto recurse = [](auto lambda) {
    return [lambda](auto&&... args) {
        return lambda(lambda, std::forward<decltype(args)>(args)...);
    };
};

auto my_recursive_lambda = recurse([](auto self, std::map<int, int>& memo, int n) {
    if (n == 0) {
        return 1;
    } else if (n < 0) {
        return 0;
    }

    auto find = memo.find(n);
    if (find != memo.end()) {
        return find->second;
    }

    int num_steps = self(self, memo, n - 1) + self(self, memo, n - 2) + self(self, memo, n - 3);

    memo[n] = num_steps;

    return num_steps;
});

my_recursive_lambda(memo, n); // magic!

If you really need this for c++11, you will need std::function:

auto recurse = std::function<int(std::map<int, int>&, int)>{};

recurse = [&recurse](std::map<int, int>& memo, int n) {
    // same as you tried.
}

Or if you give up convenience, you can hand roll your lambda type:

struct {
    auto operator()(std::map<int, int>& memo, int n) -> int {
        auto&& recurse = *this;
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            return 0;
        }

        auto find = memo.find(n);
        if (find != memo.end()) {
            return find->second;
        }

        //int num_steps = recurse(n - 1) + recurse(n - 2) + recurse(n - 3); // attempt (1) or (2)
        int num_steps = recurse(memo, n - 1) + recurse(memo, n - 2) + recurse(memo, n - 3); // attempt (3)

        memo[n] = num_steps;

        return num_steps;
    }
} recurse{};

Can you capture a reference in a recursive lambda?

3 Answers3