Tail recursive function to find arithmetic sum in C++/C

.cpp

/*
TL;DR: Compile the program as follows:
------
  
      g++ add.cpp -O2 && ./a.out


RIGOROUS DISCUSSION:
--------------------
Suppose you want to compute the sum of the series:

  n, n - 1, n - 2, ..., 2, 1.
  
  METHOD 1:
  ---------
  The most efficient way to compute the sum of such a series is by finding the
  [arithmetic sum](https://en.wikipedia.org/wiki/Arithmetic_progression#Sum) 
  
  METHOD 2:
  ---------
  However, for kicks, you could also recursively compute the sum. A naiive recursive
  function to copute the arithmetic sum would look as follows:
  
  unsigned long long int add(unsigned long long int n) {
    if (n == 0) {
      return n;
    }

    return n + add (n - 1);
  }
  
  The problem with this approach, of course, is that:
    - recursion essentially involves function calls.
    - each function call involves the creation of a new activation stack
    - each new activation stack is created in the stack memory
    - stack memory is limited
    - for extremely large values of `n`, stack overflows **will** occur
    
  ANALYSIS:
  ---------
    In the naiive recursion example, there is a "need" to "return to the caller"
    which is created through the `return` statement:
        
        return n + add(n - 1);
    
    Through the operation of addition with `n`, the statement necessitates the
    return of the call, `add(n - 1)`, to the caller. How else will it compute
    the sum `n + add(n - 1)`!

  METHOD 3:
  ---------
  In order to get around the practical obstacle of having to return to the caller,
  we can "tell" the callee what the value that we want to add the expression, `add(n - 1)`
  is.
  
  That is, can we coerce the `return` statement to possess the following form?
  
      return add(a, b);
      
  This would eliminate the need to return to the caller:
    - the `return` statement is the last statement in the caller.
    - there is nothing to do after the execution of the `return` statement;
      the compiler is *perhaps* smart enough to know this.
    - by eliminating the need to return to the caller, the compiler can
      also elimiate the creation of new activation stacks!
    - by eliminating the need to create new activation stacks, the compiler
      achieves two important results:
        - saves an incredible amount of stack memory; the space that `n`
          function stack frames would have needed will be reduced to that
          of `1`.
        - presumably saves a lot of time that would otherwise be wasted
          in the creation of new activation stacks (allocating a new region
          in stack space, setting up variables in it, etc).

  Such an elimination is called "tail call elimination" because it happens
  at the tail of the recursive call.

  ANALOGY WITH GRAPHS:
  --------------------
  The idea of tail call elimination is essentially a graph problem where you
  go from `source` to `destination`, where each node is a recursive function
  call. When you get to the `destination` you do not look back because there
  is nothing at the immediately previous location that is of interest to you.
  
      add (a, b) --> add (c, d) ---> ... --> add (y, z)

  Contrast this with a graph that represents naiive recursion, where there
  exists the need to return to the caller because it contains crucial information
  for the success of the latter's `return` statement:
  
      add (a) <==> add (a - 1) <==> ... <==> add (0)

SUMMARY:
--------
  - recursive calls involve the creation of new stack frames in stack memory
  - stack memory is limited; it's only a matter of time before recursive calls
    reach a depth where they cause stack overflow
  - naiive recursion often involves the need to return to the caller in order
    to formally complete expressions.
  - we can eliminate this need to return to the caller as long as the following
    two requirements are met:
      1) the caller can "tell" the callee everything it needs to know in advance
        (i.e. through the argument list) so as to avoid returning to the caller.
      2) the compiler supports tail-call elimination.
        - for example, in using `gcc`, you need to specify optimization levels `O2`
          or `O3` for the compiler to eliminate tail calls.
        - some compilers such as older versions of the Ruby MRI did not support
          tail-call elimination, so recursive programs can very easily crash
          despite satisfying condition 1).
        - it's also worth noting that functional progrmamming language implementations
          are often **required** to be tail-call optimized because recursion is the only
          way to iterate, so optimizing it is paramount.
   
SUGGESTION ON HOW TO THINK TAIL RECURSIVELY:
--------------------------------------------

Try to determine how to effectively "tell" the callee everything it needs to know.
*/

#include <iostream>

unsigned long long int add(unsigned long long int n, unsigned long long int a) {
  if (n == 0) {
    return a;
  }

  /* By passing `n + a`, the caller is effectively "telling" the callee what
     it needs to add `n - 1` with.
  */
  return add (n - 1, n + a);
}

int main() {
  std::cout << add(10000000000, 0) << "\n";

  return 0;
}