C++2a recursive lambda within a function

Question

I am trying to get this to compile:

#include <algorithm>
#include <climits>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;


bool isInterleave(string &s1, string &s2, string &s3) {
  auto dfs = [&](int i, int j, int k) {
    if (k > s3.length()) {
      return true;
    }
    if (s1[i] == s3[k]) {
      auto res = dfs(i + 1, j, k + 1);

    }
  };

  dfs(0, 0);
}

I get an error:


x86-64 gcc 9.3

-pedantic -Wall -O2 -std=c++2a
Could not execute the program

Compiler returned: 1

Compiler stderr

<source>: In lambda function:

<source>:14:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

   14 |     if (k > s3.length()) {

      |         ~~^~~~~~~~~~~~~

<source>:18:18: error: use of 'dfs' before deduction of 'auto'

   18 |       auto res = dfs(i + 1, j, k + 1);

      |                  ^~~

<source>: In function 'bool isInterleave(std::string&, std::string&, std::string&)':

<source>:23:11: error: no match for call to '(isInterleave(std::string&, std::string&, std::string&)::<lambda(int, int, int)>) (int, int)'

   23 |   dfs(0, 0);

      |           ^

<source>:13:14: note: candidate: 'isInterleave(std::string&, std::string&, std::string&)::<lambda(int, int, int)>'

   13 |   auto dfs = [&](int i, int j, int k) {

      |              ^

<source>:13:14: note:   candidate expects 3 arguments, 2 provided

<source>:24:1: warning: no return statement in function returning non-void [-Wreturn-type]

   24 | }

      | ^

How do I fix this?

You can't use `dfs` until its type has been determined, and you left it to the compiler to work out what it returns, which it can't until it has determined what it returns. — molbdnilo, May 08 '20 at 12:19
You have also forgotten that a function that is supposed to return something must do that. — molbdnilo, May 08 '20 at 12:21
Does this answer your question? [Recursive lambda functions in C++11](https://stackoverflow.com/questions/2067988/recursive-lambda-functions-in-c11) — bitmask, May 08 '20 at 13:04

Ted Lyngmo · Answer 1 · 2022-09-07T22:46:16.423

'dfs' declared with deduced type 'auto' cannot appear in its own initializer

With recursive lambdas you can use std::function to provide the signature so it doesn't have to be deduced:

#include <functional>
#include <string>

bool isInterleave(std::string &s1, std::string &s2, std::string &s3) {

  std::function<bool(int, int, int)> dfs = [&](int i, int j, int k) {
    if (k > s3.length()) {
      return true;
    }

    // what should the function return if you get this far?
    if (s1[i] == s3[k]) {
      // should it return this?
      auto res = dfs(i + 1, j, k + 1);
    }

    // or false?
  };

  /* return? */ dfs(0, 0);
}

In C++23, the feature "Deducing this" P0847 will make it possible to define your lambda as such:

auto dfs = [&](this auto& me, int i, int j, int k) -> bool {
    if (k > s3.length()) return true;
    if (s1[i] == s3[k]) return me(i + 1, j, k + 1);
    return false;
};

score 4 · Answer 2 · answered May 08 '20 at 12:44

Some problems not directly related to your question: You are not returning from all paths in the lambda, dfs(0,0) is too little parameters and isInterleave returns nothing. I simply added some return statements without paying attention to the logic.

As mentioned in a comment, you cannot (directly) use the lambda before its type is known. With a level of indirect it can be done:

bool isInterleave(string &s1, string &s2, string &s3) {
  auto dfs = [&](auto F,int i, int j,int k) {
        if (k > s3.length()) {
          return true;
        }
        if (s1[i] == s3[k]) {
            return F(F,i + 1, j, k + 1);     
        }
        else return false;
  };
  return dfs(dfs,0, 0,0);
}

A simpler example to see that this actually works:

#include <iostream>

int main(){ 
    auto recurse = [](auto F,int i,int j){
        if (i == 0) return j;
        return F(F,i-1,j+i);
    };

    std::cout << recurse(recurse,5,0);

}

Output: 15 ( = 5+4+3+2+1+0)

When looking at your answer Today, I find it extremely similar to what will actually be added in C++23 as _"Deducing this"_ where your `auto F` is `this auto&`. +1 — Ted Lyngmo, Sep 07 '22 at 22:48

C++2a recursive lambda within a function

2 Answers2