title: Tail recursion in R
body: <p>I seem to misunderstand tail recursion; according <a href="https://stackoverflow.com/questions/13208963/tail-recursion-on-r-statistical-environment">to this stackoverflow question</a> R does not support tail recursion. However, let's consider the following functions to compute the nth fibonacci number:</p>
  
  <p>Iterative version:</p>
  
  <pre><code>Fibo &lt;- function(n){
      a &lt;- 0
      b &lt;- 1
      for (i in 1:n){
          temp &lt;- b
          b &lt;- a
          a &lt;- a + temp
      }
      return(a)
  }
  </code></pre>
  
  <p>"Naive" recursive version:</p>
  
  <pre><code>FiboRecur &lt;- function(n){
      if (n == 0 || n == 1){
          return(n)
      } else {
          return(FiboRecur(n-1) + FiboRecur(n-2))
          }
  }
  </code></pre>
  
  <p>And finally an example I found that should be tail call recursive:</p>
  
  <pre><code>FiboRecurTail &lt;- function(n){
      fib_help &lt;- function(a, b, n){
          if(n &gt; 0){
              return(fib_help(b, a+b, n-1))
          } else {
              return(a)
          }
      }
      return(fib_help(0, 1, n))
  }
  </code></pre>
  
  <p>Now if we take a look at the traces when these functions are called, here is what we get:</p>
  
  <pre><code>Fibo(25)
  trace: Fibo(25)
  [1] 75025
  
  
  trace(FiboRecur)
  FiboRecur(25)
  Thousands of calls to FiboRecur and takes a lot of time to run
  
  FiboRecurTail(25)
  trace: FiboRecurTail(25)
  [1] 75025
  </code></pre>
  
  <p>In the cases of <code>Fibo(25)</code> and <code>FiboRecurTail(25)</code>, the answer is displayed instantaneously and only one call is made. For <code>FiboRecur(25)</code>, thousands of calls are made and it runs for some seconds before showing the result. </p>
  
  <p>We can also take a look at the run times using the <code>benchmark</code> function from the package <code>rbenchmark</code>:</p>
  
  <pre><code>benchmark(Fibo(30), FiboRecur(30), FiboRecurTail(30), replications = 5)
                 test replications elapsed relative user.self sys.self user.child sys.child
  1          Fibo(30)            5    0.00       NA     0.000        0          0         0
  2     FiboRecur(30)            5   13.79       NA    13.792        0          0         0
  3 FiboRecurTail(30)            5    0.00       NA     0.000        0          0         0
  </code></pre>
  
  <p>So if R does not support tail recursion, what is happening in <code>FiboRecurTail(25)</code> that makes it run as fast as the iterative version while the "naive" recursive function runs like molasses? Is it rather that R supports tail recursion, but does not optimize a "naive" recursive version of a function to be tail-call recursive like other programming languages (Haskell for instance) do? This is what I understand from this <a href="https://stat.ethz.ch/pipermail/r-devel/2011-April/060598.html" rel="nofollow noreferrer">post in R's mailing list</a>.</p>
  
  <p>I would greatly appreciate if someone would shed some light into this. Thanks!</p>