git » homepage.git » master » tree

<html>
  <head>
    <title>Tail Recursion in R with Trampolines - wondr</title>
    <link rel="stylesheet" href="../style.css"/>
    <link rel="stylesheet" href="../code_highlight.css"/>
    <link rel="alternate" type="application/atom+xml" href="../atom.xml"/>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
  </head>
  <body class="page">
    <div class="site">
      <header id="header" class="header-container">
        <div class="site-header">
          <nav id="navmenu" aria-label="Main Menu">
            <ul class="main-menu">
              <li>
                <a href=".." aria-current="page">Index</a>
              </li>
            </ul>
          </nav>
          <div class="site-info">
            <h1 class="site-title title">Wondr</h1>
            <p class="site-description">Wondering about R</p>
          </div>
        </div>
      </header>
      <main class="main">
        <article lang="en" class="entry">
          <header class="entry-header">
            <div class="entry-info">
              <h1 class="entry-title title">Tail Recursion in R with Trampolines</h1>
            </div>
            <div class="meta">
              <span class="posted-on">
                <svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
                  <rect x="3" y="4" width="18" height="18" rx="2" ry="2"></rect>
                  <line x1="16" y1="2" x2="16" y2="6"></line>
                  <line x1="8" y1="2" x2="8" y2="6"></line>
                  <line x1="3" y1="10" x2="21" y2="10"></line>
                </svg>
                <span class="screen-reader">Posted on </span>
                <time class="date" datetime="2017-10-13T00:00:00Z">2017-10-13</time>
              </span>
              <span class="reading-time">
                <svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
                  <circle cx="12" cy="12" r="10"></circle>
                  <polyline points="12 6 12 12 15 15"></polyline>
                </svg>
                5 minute read
              </span>
            </div>
          </header>
          <div class="entry-content">
<p>I recently enjoyed participating in a <a href="https://community.rstudio.com/t/tidiest-way-to-do-recursion-safely-in-r/1408">discussion about recursion in R</a> on the new <a href="https://community.rstudio.com/">RStudio Community</a> site, and I thought to inaugurate my blog with a post inspired by the discussion.</p>
<p>R supports recursive functions, but does not optimize <a href="https://en.wikipedia.org/wiki/Tail_call"><em>tail recursive</em></a> functions the way some other languages do. Fortunately, with a mechanism known as a <a href="https://en.wikipedia.org/wiki/Trampoline_(computing)#High-level_programming"><em>trampoline</em></a>, the R programmer can implement something like the optimization manually and with very little code.</p>
<p>To understand trampolines, one must first understand the mechanics of function calls and recursion.</p>
<h3 id="the-call-stack">The Call Stack</h3>
<p>As in many other languages, functions in R may call themselves. For example, here is a recursive function that decrements its argument until 0 is reached:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb1-1"><a href="#cb1-1"></a>countdown &lt;-<span class="st"> </span><span class="cf">function</span>(n) <span class="cf">if</span> (n <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span>) <span class="kw">countdown</span>(n<span class="dv">-1</span>) <span class="cf">else</span> <span class="st">&quot;done&quot;</span></span></code></pre></div>
<p>This function has no problem with small values of <code>n</code>:</p>
<pre><code>&gt; countdown(10)
[1] &quot;done&quot;
&gt; countdown(100)
[1] &quot;done&quot;
&gt; countdown(1000)
[1] &quot;done</code></pre>
<p>Unfortunately, when <code>n</code> is big enough, an error is raised:</p>
<pre><code>&gt; countdown(10000)
Error: C stack usage  7969236 is too close to the limit</code></pre>
<p>The problem here is that the top-most invocation of the <code>countdown</code> function, the one we called with <code>countdown(10000)</code>, can’t return until <code>countdown(9999)</code> returned, which can’t return until <code>countdown(9998)</code> returned, and so on.</p>
<p>R keeps track of all of these calls in a data structure called <em>the call stack</em> or sometimes just <em>the stack</em>. The stack contains references to all outstanding function calls, recursive or not.</p>
<p>Since the stack is stored in memory, and since computers only have so much memory, the number of nested calls that can occur in a program is limited.</p>
<p>If we want to decrement a number 10000 or more times and print something when we’re done, we have to do it a different way. That way is to use a loop.</p>
<h3 id="loops">Loops</h3>
<p>Here’s the <code>countdown</code> function using a loop instead of recursion:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb4-1"><a href="#cb4-1"></a>countdown &lt;-<span class="st"> </span><span class="cf">function</span>(n) {</span>
<span id="cb4-2"><a href="#cb4-2"></a>  <span class="cf">while</span> (n <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span>) n &lt;-<span class="st"> </span>n<span class="dv">-1</span>;</span>
<span id="cb4-3"><a href="#cb4-3"></a>  <span class="st">&quot;done&quot;</span></span>
<span id="cb4-4"><a href="#cb4-4"></a>}</span></code></pre></div>
<p>It doesn’t <em>overflow</em> the stack:</p>
<pre><code>&gt; countdown(10000)
[1] &quot;done&quot;</code></pre>
<p>The new <code>countdown</code> contains the same essential pieces as the recursive version: the <code>n &gt; 0</code> test, decrementing <code>n</code>, and returning <code>"done"</code> at the end. The pieces are just slightly differently arranged so that <code>countdown</code> doesn’t need to call itself.</p>
<p>If it does what we want, and looks only slightly different than the recursive version… why did we care about recursion again?</p>
<p>Well, maybe we don’t. The choice to use recursion is a stylistic one with arguable benefits. People with a mathematical bent seem to enjoy it. So do I, usually.</p>
<p>Forgoing a debate of the merits of recursive style, let’s assume we want it, and continue on to trampolines: a means to stack-friendly recursive functions.</p>
<h3 id="trampoline">Trampoline</h3>
<p>A trampoline is a function or set of functions that together give us the tools we need to write code in a recursive style, in a way that doesn’t overflow the stack. Here’s an awesome trampoline by <a href="http://www.jimhester.com/">Jim Hester</a>:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb6-1"><a href="#cb6-1"></a>trampoline &lt;-<span class="st"> </span><span class="cf">function</span>(f, ...) {</span>
<span id="cb6-2"><a href="#cb6-2"></a>  <span class="cf">function</span>(...) {</span>
<span id="cb6-3"><a href="#cb6-3"></a>    ret &lt;-<span class="st"> </span><span class="kw">f</span>(...)</span>
<span id="cb6-4"><a href="#cb6-4"></a>    <span class="cf">while</span> (<span class="kw">inherits</span>(ret, <span class="st">&quot;recursion&quot;</span>)) {</span>
<span id="cb6-5"><a href="#cb6-5"></a>      ret &lt;-<span class="st"> </span><span class="kw">eval</span>(<span class="kw">as.call</span>(<span class="kw">c</span>(f, <span class="kw">unclass</span>(ret))))</span>
<span id="cb6-6"><a href="#cb6-6"></a>    }</span>
<span id="cb6-7"><a href="#cb6-7"></a>    ret</span>
<span id="cb6-8"><a href="#cb6-8"></a>  }</span>
<span id="cb6-9"><a href="#cb6-9"></a>}</span>
<span id="cb6-10"><a href="#cb6-10"></a></span>
<span id="cb6-11"><a href="#cb6-11"></a>recur &lt;-<span class="st"> </span><span class="cf">function</span>(...) {</span>
<span id="cb6-12"><a href="#cb6-12"></a>  <span class="kw">structure</span>(<span class="kw">list</span>(...), <span class="dt">class =</span> <span class="st">&quot;recursion&quot;</span>)</span>
<span id="cb6-13"><a href="#cb6-13"></a>}</span></code></pre></div>
<p>Using it, <code>countdown</code> now looks like this:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb7-1"><a href="#cb7-1"></a>countdown &lt;-<span class="st"> </span><span class="kw">trampoline</span>(<span class="cf">function</span>(n) {</span>
<span id="cb7-2"><a href="#cb7-2"></a>  <span class="cf">if</span> (n <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span>) <span class="kw">recur</span>(n<span class="dv">-1</span>) <span class="cf">else</span> <span class="st">&quot;done&quot;</span></span>
<span id="cb7-3"><a href="#cb7-3"></a>})</span></code></pre></div>
<p>It’s <strong>very close</strong> stylistically to the original recursive version, but has no stack issues:</p>
<pre><code>&gt; countdown(10000)
[1] &quot;done&quot;</code></pre>
<p>The trampoline works because it’s thin veneer over a regular loop. Compared to our direct loop version of <code>countdown</code>, the <em>body</em> of the trampoline’s <code>while</code> is parameterized by the <code>f</code> function instead of being hard-coded.</p>
<p>The only new requirement of this re-arrangement is that the <em>body</em>, or the <code>f</code> function, return <code>recur</code> instead of calling itself if it wants to keep going.</p>
<p>In languages that perform this optimization automatically, applicable cases are recognized by the compiler and the recursive code is rewritten as a loop. Compilers that do this are said to perform <em>TCO</em>, where TCO stands for tail-call optimization.</p>
<h3 id="tail-call-conversion">Tail call conversion</h3>
<p>Trampolines only apply to <a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)#single_recursion">singly-recursive</a> functions that call themselves in tail position, but many algorithms commonly expressed do not meet these criteria. For example, here’s a recursive <code>factorial</code> function in R that can’t immediately be trampolined:</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb9-1"><a href="#cb9-1"></a>factorial &lt;-<span class="st"> </span><span class="cf">function</span>(n) <span class="cf">if</span> (n <span class="op">==</span><span class="st"> </span><span class="dv">0</span>) <span class="dv">1</span> <span class="cf">else</span> n<span class="op">*</span><span class="kw">factorial</span>(n<span class="dv">-1</span>)</span></code></pre></div>
<blockquote>
<p>Note: It probably wouldn’t make sense to trampoline this function without other modifications first, because <code>n</code> is coerced to the <code>numeric</code> class if it wasn’t already. For medium-sized <code>n</code>, the numeric (double precision) <code>n</code> overflows to <code>Inf</code> before the stack overflows. The <a href="https://cran.r-project.org/web/packages/gmp/index.html">gmp</a> library might be a way to produce the necessary large integers. I’ll use <code>factorial</code> anyway because it’s a compact function and the transformation is clear.</p>
</blockquote>
<p>The “tail” of <code>factorial</code> is the expression <code>n*factorial(n-1)</code>, which places a call to <code>factorial</code> on the stack before returning. This is exactly the operation that eventually leads to stack overflow and that we need to eliminate.</p>
<p>The way forward is to introduce an <em>accumulator</em>, or a variable to store intermediate state between calls. It’s a step towards an explicit loop, but with R’s named and default argument support, can be done in a decidedly un-loopy way:</p>
<div class="sourceCode" id="cb10"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb10-1"><a href="#cb10-1"></a>factorial &lt;-<span class="st"> </span><span class="cf">function</span>(n, <span class="dt">prod =</span> <span class="dv">1</span>) {</span>
<span id="cb10-2"><a href="#cb10-2"></a>  <span class="cf">if</span> (n <span class="op">==</span><span class="st"> </span><span class="dv">0</span>) prod <span class="cf">else</span> <span class="kw">factorial</span>(n<span class="dv">-1</span>, n<span class="op">*</span>prod)</span>
<span id="cb10-3"><a href="#cb10-3"></a>}</span></code></pre></div>
<p>Instead of relying on a recursive call for the number to multiply <code>n</code> by, we store it explicitly in the <code>prod</code> argument and pass it along. In this way the running product is maintained across invocations and the stack doesn’t need to grow.</p>
<p>Of course, in R, the stack does grow, but now we’ve refactored the function sufficiently enough to apply <code>trampoline</code>. Let’s do that:</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb11-1"><a href="#cb11-1"></a>factorial &lt;-<span class="st"> </span><span class="kw">trampoline</span>(<span class="cf">function</span>(n, <span class="dt">prod =</span> <span class="dv">1</span>) {</span>
<span id="cb11-2"><a href="#cb11-2"></a>  <span class="cf">if</span> (n <span class="op">==</span><span class="st"> </span><span class="dv">0</span>) prod <span class="cf">else</span> <span class="kw">recur</span>(n<span class="dv">-1</span>, n<span class="op">*</span>prod)</span>
<span id="cb11-3"><a href="#cb11-3"></a>})</span></code></pre></div>
<h3 id="mutual-recursion">Mutual recursion</h3>
<p>Jim’s trampoline is really efficient, but can’t handle interdependent, <em>mutually recursive</em> functions. These are functions that call one another.</p>
<p>Arrangements like this don’t come up much in my experience, and require a different kind of trampoline, and so I generally prefer solutions like Jim’s. One type of program where mutual recursion seems to come up is in <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser">parsers</a>.</p>
<p>But just for completeness, here’s a <code>trampoline</code> function and two mutually recursive functions from <a href="https://mitpress.mit.edu/sicp/full-text/sicp/book/node82.html">SICP</a>:</p>
<div class="sourceCode" id="cb12"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb12-1"><a href="#cb12-1"></a>trampoline &lt;-<span class="st"> </span><span class="cf">function</span>(f, ...) {</span>
<span id="cb12-2"><a href="#cb12-2"></a>  <span class="cf">function</span>(...) {</span>
<span id="cb12-3"><a href="#cb12-3"></a>    ret &lt;-<span class="st"> </span><span class="kw">f</span>(...)</span>
<span id="cb12-4"><a href="#cb12-4"></a>    <span class="cf">while</span> (<span class="kw">is.function</span>(ret)) ret &lt;-<span class="st"> </span><span class="kw">ret</span>();</span>
<span id="cb12-5"><a href="#cb12-5"></a>    ret</span>
<span id="cb12-6"><a href="#cb12-6"></a>  }</span>
<span id="cb12-7"><a href="#cb12-7"></a>}</span>
<span id="cb12-8"><a href="#cb12-8"></a></span>
<span id="cb12-9"><a href="#cb12-9"></a>even &lt;-<span class="st"> </span><span class="kw">trampoline</span>(<span class="cf">function</span>(n) {</span>
<span id="cb12-10"><a href="#cb12-10"></a>  <span class="cf">if</span> (n <span class="op">==</span><span class="st"> </span><span class="dv">0</span>) <span class="ot">TRUE</span> <span class="cf">else</span> <span class="cf">function</span>() <span class="kw">odd</span>(n<span class="dv">-1</span>)</span>
<span id="cb12-11"><a href="#cb12-11"></a>})</span>
<span id="cb12-12"><a href="#cb12-12"></a></span>
<span id="cb12-13"><a href="#cb12-13"></a>odd &lt;-<span class="st"> </span><span class="kw">trampoline</span>(<span class="cf">function</span>(n) {</span>
<span id="cb12-14"><a href="#cb12-14"></a>  <span class="cf">if</span> (n <span class="op">==</span><span class="st"> </span><span class="dv">0</span>) <span class="ot">FALSE</span> <span class="cf">else</span> <span class="cf">function</span>() <span class="kw">even</span>(n<span class="dv">-1</span>)</span>
<span id="cb12-15"><a href="#cb12-15"></a>})</span></code></pre></div>
<h3 id="conclusion">Conclusion</h3>
<p>Thanks for reading, I hope you enjoyed! In summary:</p>
<ul>
<li>A certain kind of recursive function, tail recursive, can be mechanically transformed into a loop and so not consume stack space.</li>
<li>In languages that don’t perform the transformation automatically, it can be applied manually by the programmer using a <em>trampoline</em>.</li>
<li>Some recursive functions can be transformed to tail recursive functions with the introduction of <em>accumulator</em> variables, which are facilitated by R’s support for named arguments.</li>
<li>Mutually-recursive functions can also be trampolined.</li>
</ul>
          </div>
        </article>
        <article data-sblg-article="1" class="entry-content"></article>
      </main>
      <footer id="footer" class="footer-container">



        <div class="footer">

<div class="social">
  <nav aria-label="Social Menu">
    <ul class="social-menu"><li>
      <a href="mailto:alan@tailrecursion.com" >
          <span class="screen-reader">Send E-mail</span>
          <svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
  
  <path d="M4 4h16c1.1 0 2 .9 2 2v12c0 1.1-.9 2-2 2H4c-1.1 0-2-.9-2-2V6c0-1.1.9-2 2-2z"></path>
  <polyline points="22,6 12,13 2,6"></polyline>
  
</svg>

        </a>
      </li><li>
        <a href="https://github.com/alandipert/wondr-blog" >
          <span class="screen-reader">Open Github account</span>
          <svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
  
  <path d="M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37 0 0 0-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44 0 0 0 20 4.77 5.07 5.07 0 0 0 19.91 1S18.73.65 16 2.48a13.38 13.38 0 0 0-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07 0 0 0 5 4.77a5.44 5.44 0 0 0-1.5 3.78c0 5.42 3.3 6.61 6.44 7A3.37 3.37 0 0 0 9 18.13V22"></path>
  
</svg>

        </a>
      </li>

<li>
        <a href='https://twitter.com/alandipert' target='_blank' rel='noopener'>
          <span class='screen-reader'>Open Twitter account in new tab</span><svg class='icon' viewbox='0 0 24 24' stroke-linecap='round' stroke-linejoin='round' stroke-width='2' aria-hidden='true'>
  
  <path d="M23 3a10.9 10.9 0 0 1-3.14 1.53 4.48 4.48 0 0 0-7.86 3v1A10.66 10.66 0 0 1 3 4s-4 9 5 13a11.64 11.64 0 0 1-7 2c9 5 20 0 20-11.5a4.5 4.5 0 0 0-.08-.83A7.72 7.72 0 0 0 23 3z"/>
  
</svg>
</a>
      </li>
    </ul>
  </nav>
</div>
        </div>
      </footer>
    </div>
  </body>
</html>