Selecting subset of size k using recursion
Your logic is good, and the API is pretty solid as well. There are a few point that could use some work.

Organization

selectRec can be moved inside of selectSubset to simplify the structure slightly.

It's also tail recursive, so you might as well add the annotation. I cannot recall if this is required, but even if it's not, it's a good habit to get into.

For readability, I'd recommend reversing the if so that the one-liner is in the if clause rather than the else clause. Generally speaking, it's easier to keep track of what part of the code it belongs to, the closer it is to the construct - particularly if there is a bunch of nesting. Here it doesn't make a big difference, but as a matter of course I'd swap them.

Return Types &amp; Misc

As you are forgetting everything except acc when we return, we can actually simplify the return type to just Seq[O]. 

I'm going to assume that Seq was intended, so candidates - next, acc + next needs to become candidates.filter(_ == next), acc :+ next.

As the name of the trait was dropped from the question, I'm going to use GreedySubset.

Early Termination

What you have marked as an "early termination" is just "termination", it's the base case. Limiting this to the length of candidates isn't really early termination. A similar effect could be achieved by replacing k in the selectRec call inside selectSubset with k min candidates.length.

If you want to the library users to terminate early, which is not a bad idea, one way is to have selectNext return Option[O] rather than just O.

Refactored Version

import scala.annotation.tailrec

trait GreedySubset {
  type O /* Individual objects */
  type S /* Intermediate state */

  def selectSubset(candidates: Seq[O], k: Int): Seq[O] = {
    @tailrec
    def loop(candidates: Seq[O], acc: Seq[O], count: Int, state: S): Seq[O] =
      if (candidates.isEmpty || count &lt;= 0) acc
      else selectNext(candidates, acc, state) match {
        case Some(next) =&gt;
          loop(candidates.filterNot(_ == next),
            acc :+ next,
            count - 1,
            computeState(state, next))
        case None =&gt; acc
      }
    loop(candidates, Seq[O](), k, initialState(candidates))
  }

  /* Implemented by library users */
  def initialState(candidates: Seq[O]): S

  def selectNext(candidates: Seq[O], alreadySelected: Seq[O], state: S): Option[O]

  def computeState(previousState:S, lastSelected:O): S
}


Alternate Implementation

Another alternative, which is arguably simpler, is to implement this as a case class with function arguments. This implementation is exactly equivalent to the refactored version above, and is arguably simpler and easier to use.

case class GreedySelector[E,S](
  initialState: Seq[E] =&gt; S,
  selectNext: (Seq[E], Seq[E], S) =&gt; Option[E], // First argument is candidates
  computeState: (S, E) =&gt; S) {

  def selectSubset(candidates: Seq[E], k: Int): Seq[E] = {
    @tailrec
    def loop(candidates: Seq[E], acc: Seq[E], count: Int, state: S): Seq[E] =
      if (candidates.isEmpty || count &lt;= 0) acc
      else selectNext(candidates, acc, state) match {
        case Some(next) =&gt;
          loop(candidates.filterNot(_ == next),
            acc :+ next,
            count - 1,
            computeState(state, next))
        case None =&gt; acc
      }
    loop(candidates, Seq[E](), k, initialState(candidates))
  }
}