title: Implementing isPrime in Scala using tail recursion
body: <p>I'm working on an exercise which requires me to implement isPrime in scala using tail recursion. I do have an implementation however, I'm having issues with producing the right base case.</p>
  
  <p>So my algorithm involves checking all numbers from 2 to N/2, since N/2 would be the largest factor of N.</p>
  
  <pre><code>def isPrime(n: Int): Boolean = {
      def isPrimeUntil(t: Int): Boolean = {
          if(t == 2) true
          else n % t != 0 &amp;&amp; isPrimeUntil(t - 1)
      }
  
      isPrimeUntil(n/2)
  }
  </code></pre>
  
  <p>So basically if I want to check if 15 is a prime I will check all numbers from 7 to 2.</p>
  
  <p>Here is my trace:</p>
  
  <p><code>isPrimeUntil(7) -&gt; true &amp;&amp; isPrimeUntil(6)</code>
  <code>-&gt; true &amp;&amp; isPrimeUntil(5)</code>
  <code>-&gt; false &amp;&amp; isPrimeUntil(4)</code></p>
  
  <p>Because of short-circuit evaluation, the function returns false at this point.</p>
  
  <p>However, my implementation fails for the basic case of checking if 3 is prime.</p>