遞歸構建一個向量

Question

我有一個函數f(a: A): A和一個整數N。我想編寫將返回以下矢量[A]的函數：

Vector(a, f(a), f(f(a)), f(f(f(a))), ..., f^{N}(a))

其中f^{N}表示施加f遞歸N倍。 N可能比較大。我正在尋找一種不需要倒轉數據結構或不止一次遍歷數據結構的解決方案。顯然，有很多方法可以做到這一點;我在尋找功能性，慣用性和可讀性的代碼。

Answer 1

{矢量，列表，數組，...}。迭代

def iterate[A](start: A, len: Int)(f: (A) ⇒ A): Vector[A]

產生一個 集合包含函數的重複應用開始 值。啓動包含在礦井集合F中的功能len個 元件的數量收集的開始值，該值是反覆 施加返回與序列中LEN值的集合開始， F（開始）中，f（F（開始）） ...

scala> def f(x: Int): Int = if(x%2 == 0) x/2 else 3*x+1 
f: (x: Int)Int 

scala> Vector.iterate(10000, 10)(f) 
res0: scala.collection.immutable.Vector[Int] = 
Vector(10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 704) 

或者，如果你真的想實現它自己，這裏是一個可能的解決方案

scala> def iterator[A](start: A, len: Int)(f: A => A): Vector[A] = len match { 
    | case 0 => Vector() 
    | case _ => start +: iterator(f(start), len-1)(f) 
    | } 
iterator: [A](start: A, len: Int)(f: A => A)Vector[A] 

scala> iterator(10000, 100)(f) 
res1: Vector[Int] = Vector(10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 
704, 352, 176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4) 

Answer 2

(1 to N).foldLeft(Vector(a)) { (acc, a) => acc :+ f(acc.last) }