Loops by Recursion

在面向过程和面向对象的语言中，往往提供显式的Loop方法， 利用循环条件进行控制，例如在C＋＋，Java中的一段循环来遍历一串数： bool example(){ for(int i = 0; i < NUM; i++){ if（fun（i） ＝＝ key） return true } return false }

但是，在Scala中使用这种循环方式就显得很low，而且往往要使用变量var而不是常量val，与Scala的理念相悖。在Scala中往往用TailRecursion来代替循环，我们都知道，尾递归是可以和循环体互相转化且调用后仍使用同一块栈空间，不同于普通递归，不会引起overflow的问题。 曾经对尾递归很发怵，但是今天发现了一些感觉，可以简单的使用尾递归来替代循环体。

尾递归

尾递归，即在函数末尾调用自身（一定是函数末尾），因为函数在调用其他函数时要先将当前的参数都保存在内存中，返回值的过程中一方面返回值另一方面还原上下文，回到上一级的调用它的函数。在若在函数中部进行自身的调用，表现为直接jump到另一段函数体的代码（或是自身函数）的起始，在jump之前由于自身的函数并没有返回，所以需要保存此次函数的上下文到栈之后再jump，由于递归因而不断保存上下文不断jump。

但是在尾递归中，对自身的调用是在return返回阶段，因而此次函数是返回之后再jump，返回意味着退栈，由于是已经完成此次函数之后调用，所以是退栈后jump，这时jump之后再到自身，保存上下文时可以重新用上一次调用后退栈返还的空间，因为不会累加。

下面，就用尾递归的方式实现上述循环：

def example(i: Int): Boolean = {
  if(i > NUM) false
  else if (f(i) == key) true
  else example(i + 1)
}
example(0)

事实上，在上述的问题中，尾递归的实现实质上是和循环是一样的，递归的过程实质上是对每一次循环的模拟：先检测 i 是否小于 NUM，如果大于就说明到了循环底部需要跳出，到了底部都没满足条件 （f(i) == key） 于是返回false， 在循环中就类似最后循环后没找到，return false。

在循环中，循环体是自动循环的，但是在尾递归中，是重复带入 example(i+1) 这一点是通用的。

最后，范围的上限是通过参数给出的，和循环体有点点差别吧。

综上：两者思路相同，只要考虑每一次循环的内容即可。