title: How can modern compiler optimization convert recursion into returning a constant?
body: <p>When I compile the following simple recursion code with g++, the assembly code simply returns i, as if g++ can do some algebra tricks as humans can.</p>
  
  <pre class="lang-cpp prettyprint-override"><code>int Identity(int i) {
    if (i == 1)
      return 1;
    else
      return Identity(i-1)+1;
  }
  </code></pre>
  
  <p>I don't think this optimization is about tail recursion,
  and apparently, g++ must at least do these two things:</p>
  
  <ol>
  <li>If we pass a negative value, this code will fall into a infinite loop, so is it valid for g++ to eliminate this <em>bug</em>?</li>
  <li>While it is possible to enumerate all values from 1 to INT_MAX, and then g++ can tell that this function shall return i, apparently g++ uses a smarter detection method since the compilation process is pretty fast. Therefore my problem is, how does the compiler optimization do that?</li>
  </ol>
  
  <p><strong>How to reproduce</strong></p>
  
  <pre><code>% g++ -v
  gcc version 8.2.1 20181127 (GCC)
  
  % g++ a.cpp -c -O2 &amp;&amp; objdump -d a.o
  Disassembly of section .text:
  0000000000000000 &lt;_Z8Identityi&gt;:
     0:   89 f8                   mov    %edi,%eax
     2:   c3
  </code></pre>
  
  <p><strong>Updated:</strong>
  Thanks to many people for answering the problem. I collected some discussions and updates here.</p>
  
  <ol>
  <li>The compiler uses some method to know that passing negative values leads to UB. Maybe the compiler uses the same method to do the algebra tricks.</li>
  <li><s>About the tail recursion: According to Wikipedia, my former code is NOT the tail recursion form. I have tried the tail recursion version and gcc generates the correct while loop. However, it cannot just return i as my former code does.</s></li>
  <li>Someone points out that the compiler might try to "prove" f(x) = x but I still do not know the name of the actual optimization technique used. I am interested in the exact name of such an optimization, such as common subexpression elimination (CSE) or some combination of them or whatever.</li>
  </ol>
  
  <p><strong>Updated + answered:</strong>
  Thanks to the answer below (I have marked it helpful, and also check the answer from manlio), I guess I understand how a compiler can do this in an easy way. Please see the example below.
  First, modern gcc can do something more powerful than tail recursion,
  so the code is converted into something like this:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>// Equivalent to return i
  int Identity_v2(int i) {
    int ans = 0;
    for (int i = x; i != 0; i--, ans++) {}
    return ans;
  }
  // Equivalent to return i &gt;= 0 ? i : 0
  int Identity_v3(int x) {
    int ans = 0;
    for (int i = x; i &gt;= 0; i--, ans++) {}
    return ans;
  }
  </code></pre>
  
  <p>(I guess that) the compiler can know that ans and i share the same <em>delta</em> and it also knows i = 0 when leaving the loop. Therefore, the compiler knows it should return i.
  In v3, I use the <code>&gt;=</code> operator so the compiler also checks the sign of the input for me.
  This could be much simpler than I've guessed.</p>