title: More efficient way of calculating this recurrence relation in Mathematica
body: <p><em>Verbeia opened up a rather interesting discussion on the performance of the functional programming style in Mathematica. It can be found here: <a href="https://stackoverflow.com/q/6867079/312124">What is the most efficient way to construct large block matrices in Mathematica?</a></em>)</p>
  
  <p>I'm working on a problem, and after doing some timing of my code one particularly time consuming portion is where I calculate entries of a matrix through a recurrence relation:</p>
  
  <pre><code>c = Table[0, {2L+1}, {2L+1}];
  
  c[[1, 1]] = 1;
  Do[c[[i, i]] = e[[i - 1]] c[[i - 1, i - 1]], {i, 2, 2 L + 1}];
  Do[c[[i, 1]] = (1 - e[[i - 1]]) c[[i - 1, 1]], {i, 2, 2 L + 1}];
  Do[c[[i, j]] = (1 - e[[i - 1]]) c[[i - 1, j]] + 
      e[[i - 1]] c[[i - 1, j - 1]], {i, 2, 2 L + 1}, {j, 2, i - 1}];
  </code></pre>
  
  <p>Where <code>e</code> is some externally defined list. Is there any way I could write this in a more efficient manner? I can't seem to find any obvious way of using the built in functions to accomplish this in a more idiomatic and efficient way.</p>
  
  <p>I realize I can only do so much, since this code is <code>O(n^2)</code>, but I have a series of matrix multiplications (About 6 in all) that, combined, take less time to run than this statement. Anything I can do to speed this up even slightly would make an appreciable difference in run times for me.</p>
  
  <p><strong>Update:</strong>
  In line with what <strong>acl</strong> recommended, I tried using <code>Compile</code> to speed up my expressions. For a relatively small <code>L = 600</code>, I get 3.81 seconds on the naive <code>Do[...]</code>, 1.54 seconds for plain old <code>Compile</code>, and 0.033 seconds for <code>Compile[..., CompilationTarget-&gt;"C"]</code>. </p>
  
  <p>For a more realistic size of <code>L = 1200</code>, the timings become 16.68, 0.605, and 0.132 for <code>Do</code>, <code>Compile</code> and <code>Compile[.., CompilationTarget-&gt;"C"]</code> respectively. I'm able to achieve the same 2 orders of magnitude speedup that acl mentioned in his post.</p>