title: How does prolog run through recursive queries using succ?
body: <p>Can someone explain to me why this prolog query works the way it does. The definition is:</p>
  
  <pre><code>add(0,Y,Y). 
  add(succ(X),Y,succ(Z)):- add(X,Y,Z).
  </code></pre>
  
  <p>Given this:</p>
  
  <pre><code>?-  add(succ(succ(succ(0))),  succ(succ(0)),  R).
  </code></pre>
  
  <p>Heres the trace of the query:</p>
  
  <pre><code>Call:  (6)  add(succ(succ(succ(0))),  succ(succ(0)),  R) 
  
  Call:  (7)  add(succ(succ(0)),  succ(succ(0)),  _G648) 
  
  Call:  (8)  add(succ(0),  succ(succ(0)),  _G650) 
  
  Call:  (9)  add(0,  succ(succ(0)),  _G652) 
  
  Exit:  (9)  add(0,  succ(succ(0)),  succ(succ(0))) 
  
  Exit:  (8)  add(succ(0),  succ(succ(0)),  succ(succ(succ(0)))) 
  
  Exit:  (7)  add(succ(succ(0)),  succ(succ(0)), 
                                                succ(succ(succ(succ(0))))) 
  
  Exit:  (6)  add(succ(succ(succ(0))),  succ(succ(0)), 
                                                  succ(succ(succ(succ(succ(0))))))
  </code></pre>
  
  <p>The part that confused me the most about that tutorial was the fact that in the first argument, the succ is stripped, and it recurses. While recursing though, R gains a succ... HOW?! Also, where does the zero come from at the first exit (9)? I am new to prolog, and I am trying to understand the language for a homework. Any help much appreciated.</p>
  
  <p>Note: for anyone interested, the link to this tutorial is <a href="http://www.learnprolognow.org/lpnpage.php?pagetype=html&amp;pageid=lpn-htmlse9" rel="nofollow noreferrer">http://www.learnprolognow.org/lpnpage.php?pagetype=html&amp;pageid=lpn-htmlse9</a></p>