title: What is the relationship between recursion and proof by induction?
body: <p>What is the relationship between recursion and proof by induction?</p>
  
  <p>Let's say <code>fn(n)</code>, </p>
  
  <p>recursion is <code>fn(n)</code> calls itself until meet <code>base condition</code>;</p>
  
  <p>induction is when <code>base condition</code> is meet, try to prove <code>(base case + 1)</code> is also correct.</p>
  
  <p>It seems recursion and induction are in different direction. One starts from <code>n</code> to <code>base case</code>, the other is start from <code>base case</code> to <code>infinite</code>.</p>
  
  <p>Could someone explain the idea in details?</p>