Selecting subset of size k using recursion Sometimes I need to implement recursive algorithms that pass a certain state from one recursive call to another. For example, a greedy subset selection: we have a set of candidate objects, and we select a subset of size k greedily, one-by-one. The choice depends on the already selected objects and some constantly re-computed state. This state (and the set of candidates) can be discarded, once the selection is complete.

type O /* Individual objects */
type S /* Intermediate state */

def selectSubset(candidates: Seq[O], k: Int): Seq[O] =
    selectRec(candidates, Seq[O](), k, initialState(candidates))._2

def selectRec(candidates: Seq[O], acc: Seq[O], k: Int, state: S): (Seq[O], Seq[O], Int, S) =
    if (k &gt; 0 &amp;&amp; candidates.nonEmpty) {
        val next = selectNext(candidates, acc, state)
        selectRec(candidates - next, acc + next, k - 1, computeState(state, next))
    } else {
         (null, acc, null, null) /* (Early) termination */
    }

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

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

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



Is recursion a good choice here?
Is there a neat alternative to Tuple as the return type of the recursive function? E.g. a case class might be more readable. In principle, candidates, i, and state can be merged into a single variable, but that also doesn't seem neat.
How to "express" (early) termination with tuples? We don't care about anything but acc at this point, but nulls look ugly.
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))
  }
}