title: Different stack depth for lambdas and regular functions in C++?
body: <p>Consider a normal recursive function:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;functional&gt;
  
  void f(unsigned long long int x) {
      std::cout &lt;&lt; x &lt;&lt; "\n";
      if(x &lt; 1e9)
          f(x+1);
  }
  
  int main() {
      f(1);
      return 0;
  }
  </code></pre>
  
  <p>This terminates at <strong>43033</strong>.</p>
  
  <p>Now consider a recursive lambda:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;functional&gt;
  
  int main() {
      std::function&lt;void(int)&gt; g = [&amp;g](unsigned long long int x) {
          std::cout &lt;&lt; x &lt;&lt; "\n";
          if(x &lt; 1e9)
              g(x+1);
      };
      g(1);
      return 0;
  }
  </code></pre>
  
  <p>This terminates at a much lower stack depth of <strong>11736</strong>.</p>
  
  <p>Why do lambdas have a lower max stack depth?</p>
  
  <p>(Compiling with <code>g++ (GCC) 5.4.0</code>, with <code>-std=c++14 -Wall</code>)</p>
  
  <p>Also note that compiling with <code>-O3</code> optimization allows for <strong>practically infinite</strong> recursion depth, but the lambda still terminates at <strong>25k</strong>.</p>
  
  <hr>
  
  <p><strong>EDIT</strong>: Following @Yakk, here are results with the <a href="https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/" rel="nofollow">Y-combinator</a>:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;functional&gt;
  
  using namespace std;
  
  template &lt;typename T, typename R&gt;
  function&lt;R(T)&gt; Y(function&lt;function&lt;R(T)&gt;(function&lt;R(T)&gt;)&gt; f) {
      // Y f = f (λx.(Y f) x)
      return f([=](T x) { return Y(f)(x); });
  }
  
  int main() {
      using fg = function&lt;void(int)&gt;;
      function&lt;fg(fg)&gt; sg = [](fg g) {
          return [g](unsigned long long int x) {
              std::cout &lt;&lt; x &lt;&lt; "\n";
              if(x &lt; 1e9)
                  g(x+1);
          };
      };
  
      Y(sg)(1);
      return 0;
  }
  </code></pre>
  
  <p>This terminates at <strong>4781</strong> and <strong>9221</strong> with and without <code>-O3</code> respectively.</p>