Implementing Hofstadter-Conway algorithm without raw recursion

Question

I was playing around with trying the complete the Hofstadter-Conway $10,000 sequence task in Scala on Rosetta Code. I want to use as idiomatic Scala as possible, but I'm having trouble implementing the algorithm without using raw recursion, which normally one only would use as a last resort. Here is what I currently have:

object HofstadterConway {

 def makeHCSequence(max: Int): Seq[Int] = {
   def hc(v: Vector[Int], idx: Int): Vector[Int] = {
     if (idx == (max + 1)) {
       v.tail
     } else if (idx <= 2) {
       hc(v :+ 1, idx + 1)
     } else {
       hc (v :+ (v(v(idx - 1)) + v(idx - v(idx - 1))), idx + 1)
     }
   }
   hc(Vector(), 0)
 }
}

Is there a way to do this more idiomatically?

Never mind. I figured it out. What I needed was a fold. I don't know why that didn't occur to me at first. — Garrett Rowe, Jul 15 '11 at 03:39
Somebody wrote a Scala solution here: http://rosettacode.org/wiki/Hofstadter-Conway_%2410,000_sequence — axel22, Jul 15 '11 at 08:41

Garrett Rowe · Accepted Answer · 2011-07-20T16:35:17.430

I was going to post this earlier, but I don't have enough SO cred to post answers to my own questions within 8 hours, so I had to wait. As @axel22 noted, this was part of the solution I posted on Rosetta Code website last night.

  def makeHCSequence(max: Int): Seq[Int] = 
    (0 to max - 1).foldLeft (Vector[Int]()) { (v, idx) =>
      if (idx <= 1) v :+ 1 else v :+ (v(v(idx - 1) - 1) + v(idx - v(idx - 1)))
    }

My problem was for some reason my mind got stuck trying to come up with a solution using Vector.range or Vector.iterate, the obvious choice of foldleft just wasn't occurring to me.

Implementing Hofstadter-Conway algorithm without raw recursion

1 Answers1