title: Solving recurrence relation when N is very big
body: <p>How to solve <code>recurrence</code> relation when <code>0 &lt;= N &lt;= 1,000,000,000</code> ?.</p>
  
  <p>For <strong>example</strong>, </p>
  
  <pre><code>like  d[N] = d[N-1] + d[N-2] * 3d[N-3]
  </code></pre>
  
  <p>I try to solve problem using <code>DP</code> and <code>memorization</code>, but N range is too big to making array. The input N is random. </p>
  
  <p>Is there another algorithm that I can get to the problem?.</p>