title: Can every recursion be converted into iteration?
body: <p>A <a href="http://www.reddit.com/r/programming/comments/8oh88/effectively_walking_trees_and_graphs_in_python/c09xm45" rel="noreferrer">reddit thread</a> brought up an apparently interesting question:</p>
  
  <blockquote>
    <p>Tail recursive functions can trivially be converted into iterative functions. Other ones, can be transformed by using an explicit stack. Can <em>every</em> recursion be transformed into iteration?</p>
  </blockquote>
  
  <p>The (counter?)example in the post is the pair:</p>
  
  <pre><code>(define (num-ways x y)
    (case ((= x 0) 1)
          ((= y 0) 1)
          (num-ways2 x y) ))
  
  (define (num-ways2 x y)
    (+ (num-ways (- x 1) y)
       (num-ways x (- y 1))
  </code></pre>