CODEWITHSUNDEEP
scalatail-recursion
Ming Chen
Ming Chen

Reputation: 1

Is it possible to rewrite this function tail-recursively?

I have order matching function that is written in recursive, I wonder if it is possible to turn this fuction into a tail-recursive one? and how.

Or is there a better way to improve the performance? Thanks

object CollectiveMatch extends App {


  def findSubSet(orders: List[Order], goal: (Double, Double)): List[List[Order]] = {

    var collector: List[List[Order]] = List.empty
    if (orders.isEmpty) return List.empty

    def findMatches(orders: List[Order], index: Int, current: (Double, Double), goal: (Double, Double), result: List[Order]) {
      if (orders.length < index) return
      for (i <- index until orders.length) {
        val newCurrent = if ("Buy".equals(orders(i).side)) {
          (current._1 + orders(i).qty, current._2 + orders(i).volume)
        } else {
          (current._1 - orders(i).qty, current._2 - orders(i).volume)
        }
        if (Math.abs(newCurrent._1 - goal._1) <= 0.00001 && Math.abs(newCurrent._2 - goal._2) <= 0.00001) {
          collector = collector :+ (result :+ orders(i))
        } else {
          findMatches(orders, i + 1, newCurrent, goal, result :+ orders(i))
        }
      }
    }

    findMatches(orders, 0, (0.0, 0.0), (0.0, 0.0), List.empty)
    collector
  }


  val orders = List[Order](
    Order("boc", "Buy", 75.5, 30),
    Order("jp", "Buy", 76, 120),
    Order("ocbc", "Buy", 78, 40),
    Order("sxs", "Buy", 76, 20),
    Order("icbc", "Buy", 79.5, 30),
    Order("morgan", "Buy", 80.5, 30),

    Order("eb", "Sell", 75.5, 50),
    Order("gdb", "Sell", 76.5, 50),
    Order("bocc", "Sell", 77, 80),
    Order("abc", "Sell", 80, 60),
  )

  val allSets: List[List[Order]] = findSubSet(orders, (0.0, 0.0))


}

Upvotes: 0

Views: 113

Answers (2)

Martijn
Martijn

Reputation: 12091

Yes. You will need to recurse overs List[Order] with head/tail as an "outer" recursion, and then recurse over a worklist of tails still to do of List[List[Order]] (taken from orders.tails) that you append to each time you go into an inner recursion loop.

Upvotes: 1

AminMal
AminMal

Reputation: 3173

There are ways that you can optimize and enhance your code, if you pass var collector as a function parameter to the recursive function, that way you are one step closer to what you want and It's also better in terms of functional programming ( avoid var s ), and at the end of function if you reach the break point, instead of the empty return, you can return the collector as the result. And I guess that's what you're looking for.

you can also get rid of the return keyword.

Upvotes: 0

Related Questions