转载

【Scala】尾递归优化

以递归方式思考

递归通过灵巧的函数定义，告诉计算机做什么。在函数式编程中，随处可见递归思想的运用。下面给出几个递归函数的例子：

object RecursiveExample extends App{  // 数列求和例子 defsum(xs: List[Int]):Int = if(xs.isEmpty) 1 else  xs.head + sum(xs.tail)    // 求最大值例子 defmax(xs: List[Int]):Int = if(xs.isEmpty)  throw new NoSuchElementException elseif(xs.size ==1)// 递归的边界条件  xs.head else if(xs.head > max(xs.tail)) xs.headelsemax(xs.tail)    // 翻转字符串 defstr_reverse(xs: String):String = if(xs.length ==1)  xs else  str_reverse(xs.tail) + xs.head   // 快速排序例子 defquicksort(ls: List[Int]):List[Int] = { if(ls.isEmpty)  ls else  quicksort(ls.filter(_ < ls.head)) ::: ls.head :: quicksort(ls.filter(_ > ls.head))  //quicksort(ls.filter(x => x < ls.head)) ::: ls.head :: quicksort(ls.filter(x => x > ls.head))  } }

我们以上面代码最后一个快速排序函数为例，使用递归的方式，其代码实现非常的简洁和通俗易懂。递归函数的核心是设计好递归表达式，并且确定算法的边界条件。上面的快速排序中，认为空列表就是排好序的列表，这就是递归的边界条件，这个条件是递归终止的标志。

尾递归

递归算法需要保持调用堆栈，效率较低，如果调用次数较多，会耗尽内存或栈溢出。然而，尾递归可以克服这一缺点。

尾递归是指递归调用是函数的最后一个语句，而且其结果被直接返回，这是一类特殊的递归调用。由于递归结果总是直接返回， 尾递归比较方便转换为循环 ，因此编译器容易对它进行优化。

递归求阶乘的经典例子

普通递归求解的代码如下：

deffactorial(n: BigInt): BigInt = { if(n <=1) 1 else  n * factorial(n-1) }

上面的代码，由于每次递归调用n-1的阶乘时，都有一次额外的乘法计算，这使得堆栈中的数据都需要保留。在新的递归中要分配新的函数栈。运行过程就像这样：

factorial(4) -------------- 4 * factorial(3) 4 * (3 * factorial(2)) 4 * (3 * (2 * factorial(1))) 4 * (3 * (2 * 1))

而下面是一个尾递归版本，在效率上，和循环是等价的：

importscala.annotation.tailrec  deffactorialTailRecursive(n: BigInt): BigInt = { @tailrec def_loop(acc: BigInt, n: BigInt): BigInt = if(n <=1) accelse_loop(acc*n, n-1)   _loop(1, n) }

这里的运行过程如下：

factorialTailRecursive(4) -------------------------- _loop(1, 4) _loop(4, 3) _loop(12, 2) _loop(24, 1)

该函数中的 _loop 在最后一步，要么返回递归边界条件的值，要么调用递归函数本身。

改写成尾递归版本的关键：

尾递归版本最重要的就是找到合适的累加器，该累加器可以保留最后一次递归调用留在堆栈中的数据，积累之前调用的结果，这样堆栈数据就可以被丢弃，当前的函数栈可以被重复利用。

在这个例子中，变量acc就是累加器，每次递归调用都会更新该变量，直到递归边界条件满足时返回该值。

对于尾递归，Scala语言特别增加了一个注释 @tailrec ，该注释可以确保程序员写出的程序是正确的尾递归程序，如果由于疏忽大意，写出的不是一个尾递归程序，则编译器会报告一个编译错误，提醒程序员修改自己的代码。

菲波那切数列的例子

原始的代码很简单：

deffibonacci(n: Int):Int = if(n <=2) 1 else  fibonacci(n-1) + fibonacci(n-2)

尾递归版本用了两个累加器，一个保存较小的项acc1，另一个保存较大项acc2：

deffibonacciTailRecursive(n: Int):Int = { @tailrec def_loop(n: Int, acc1: Int, acc2: Int):Int = if(n <=2)  acc2 else  _loop(n-1, acc2, acc1+acc2)   _loop(n, 1,1) }

几个列表操作中使用尾递归的例子

求列表的长度

def lengthTailRecursive[A](ls: List[A]):Int= {  @tailrec  def lengthR(result:Int, curList:List[A]):Int= curList match { caseNil=>result case_ :: tail => lengthR(result+1, tail)  }  lengthR(0, ls) }

翻转列表

def reverseTailRecursive[A](ls: List[A]):List[A] = {  @tailrec  def reverseR(result:List[A], curList:List[A]):List[A] = curList match { caseNil=>result caseh :: tail => reverseR(h ::result, tail)  }  reverseR(Nil, ls) }

去除列表中多个重复的元素

这里要求去除列表中多个连续的字符，只保留其中的一个。

// If a list contains repeated elements they should be replaced with // a single copy of the element. // The order of the elements should notbe changed. // Example: // >> compress(List('a, 'a,'a, 'a,'b, 'c,'c, 'a,'a, 'd,'e, 'e,'e, 'e)) // >> List('a, 'b,'c, 'a,'d, 'e)  defcompressTailRecursive[A](ls: List[A]):List[A] = { @tailrec defcompressR(result: List[A], curList: List[A]):List[A] = curList match {  case h :: tail => compressR(h :: result, tail.dropWhile(_ == h))  case Nil => result.reverse  }  compressR(Nil, ls) }

转载请注明作者Jason Ding及其出处

Github博客主页(http://jasonding1354.github.io/)

GitCafe博客主页(http://jasonding1354.gitcafe.io/)

CSDN博客(http://blog.csdn.net/jasonding1354)

简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)

Google搜索jasonding1354进入我的博客主页

原文 http://jasonding1354.github.io/2016/01/14/Scala/【Scala】尾递归优化/

正文到此结束