title: "Unrolling" a recursive function?
body: <p>I'm writing a path tracer in C++ and I'd like to try and implement the most resource-intensive code into CUDA or OpenCL (I'm not sure which one to pick).</p>
  
  <p>I've heard that my graphics card's version of CUDA doesn't support recursion, which is something my path tracer utilizes heavily.</p>
  
  <p>As I have it coded both in Python and C++, I'll post some simplified Python code for readability:</p>
  
  <pre><code>def Trace(ray):
    hit = what_object_is_hit(ray)
  
    if not hit:
      return Color(0, 0, 0)
  
    newRay = hit.bouceChildRayOffSurface(ray)
  
    return hit.diffuse * (Trace(newRay) + hit.emittance)
  </code></pre>
  
  <p>I tried manually unrolling the function, and there <em>is</em> a definite pattern (<code>d</code> is <code>diffuse</code> and <code>e</code> is <code>emittance</code>):</p>
  
  <pre><code>Level 1:  d1 * e1 
  
  Level 2:  d1 * d2 * e2
          + e1
  
  Level 3:  d1 * d2 * d3 * e3
          + d1 * d2 * e2
          + e1
  
  Level 4:  d1 * d2 * d3 * d4 * e4
          + d1 * d2 * d3 * e3
          + d1 * d2 * e2
          + e1
  </code></pre>
  
  <p>I might be wrong, though...</p>
  
  <p>My question is, how would I go about implementing this code in a <code>while</code> loop?</p>
  
  <p>I was thinking using something of this format:</p>
  
  <pre><code>total = Color(0, 0, 0)
  n = 1
  
  while n &lt; 10:   # Maximum recursion depth
    result = magical_function()
  
    if not result:  break
  
    total += result
    n += 1
  </code></pre>
  
  <p>I've never really dealt with the task of unraveling a recursive function before, so any help would be greatly appreciated. Thanks!</p>