斯卡拉递归

Question

我怎样才能写在常规递归和尾递归下面的函数。

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = { 
    var satisfies = 0 
    for (i <- 0 until x.length) { 
     if (test(x(i))) satisfies += 1 
    } 
    satisfies == x.length 
    } 

Answer 1

这是一个基本的递归版本。

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = 
    if (x.isEmpty) true 
    else if(test(x.head)) satisfiesAllIt(x.tail, test) && true 
    else false 

这是一个尾递归版本。

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = 
    if (x.isEmpty) true 
    else if(test(x.head)) satisfiesAllIt(x.tail, test) 
    else false 

这就是你在学习标准库之后所做的。

def satisfiesAllIt(x: List[_], test: Any => Boolean): Boolean = x.forall(test) 

---

@The原型保罗一个好点的（因为他经常做），并提供了另一种选择。

// basic recursive 
def satisfiesAllA(x: List[Any], test: Any => Boolean): Boolean = 
    x.isEmpty || satisfiesAllA(x.tail, test) && test(x.head) 

// tail recursive 
def satisfiesAllB(x: List[Any], test: Any => Boolean): Boolean = 
    x.isEmpty || test(x.head) && satisfiesAllB(x.tail, test) 

什么，我们都在家里跳舞，实际上并没有指出它是基本的和尾递归的定义区别：如果有更多的“工作”的递归调用返回（计算/评估之后进行/ etc。）则是而不是尾递归。

Answer 2

这里是satisfiesAllIt的尾递归版本。这个想法是递归地调用函数，直到列表结束并且如果测试失败返回false。

def satisfiesAllIt(x: List[Any], test: Any => Boolean): Boolean = xs match { 
    case Nil => true 
    case x :: xs => 
    if (test(x)) satisfiesAllIt(xs, test) else false 
}