algorithm - 在没有原始递归的情况下实现 Hofstadter-Conway 算法

Question

我正在尝试完成 Hofstadter-Conway $10,000 sequence Scala 中的任务 Rosetta Code .我想尽可能地使用惯用的 Scala，但是我在不使用原始递归的情况下实现算法时遇到了麻烦，通常人们只会将其用作最后的手段。这是我目前拥有的:

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)
 }
}

有没有办法更地道地做到这一点？

Answer 1

我本来打算早点发布这个，但我没有足够的信誉在 8 小时内发布我自己的问题的答案，所以我不得不等待。正如@axel22 指出的那样，这是我昨晚在 Rosetta Code 网站上发布的解决方案的一部分。

  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)))
    }

我的问题是出于某种原因，我的思绪在尝试使用 Vector.range 或 Vector.iterate 提出解决方案时停滞不前，我没有想到 foldleft 的明显选择。