如何迭代这个尾递归方法？

Question

在下面的Scala方法中,List如何xs遍历方法nth？xs.tail是递归调用,但为什么尾部不总是相同的值,因为def tail在trait中List只返回参数化类型列表？

object nth {

  def nth[T](n: Int, xs: List[T]): T =
    if (xs.isEmpty) throw new IndexOutOfBoundsException
    else if (n == 0) xs.head
    else {
        nth(n - 1, xs.tail)
        }                                 //> nth: [T](n: Int, xs: week4.List[T])T
  val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))
  nth(2 , list)   > res0: Int=3   
}

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}
class Cons[T](val head: T, val tail: List[T]) extends List[T]{
  def isEmpty = false
}
class Nil[T] extends List[T]{
  def isEmpty = true
  def head : Nothing = throw new NoSuchElementException("Nil.head")
  def tail : Nothing = throw new NoSuchElementException("Nil.tail")
}     

Answer 1

这List是一个递归结构.请参阅有关Cons的维基百科文章.这是来自那篇文章:

你要开始的结构是new Cons(42, new Cons(69, new Cons(613, new Nil))).虽然该tail方法还返回一个实例List[Int],即不是相同的列表,但是返回其中一个右指向箭头的子列表.

所以,如果在你的榜样,你会下手Cons(1, Cons(2, Cons(3, Nil))),让n会2.

• 在函数的第一次迭代中nth,我们问:是Cons(1, Cons(2, Cons(3, Nil)))空的吗？没有!是n == 0吗？不.所以用尾巴n递减并递减.
• 在第二次迭代中,我们问:是Cons(2, Cons(3, Nil))空的(这又是一次List[Int])？不是n == 0吗？不(1现在).转到下一个递归.
• 在第三次迭代中,我们问:是Cons(3, Nil)空的吗？不,是n == 0.是! 因此,返回头的Cons(3, Nil)这是3.