尾递归函数

在本节中，我们将学习如何创建尾递归（tail recursive）函数，以及如何使用@annotation.tailrec注解，这将指示编译器应用任何进一步的优化。

如何定义尾递归函数？在下面的示例中，我们定义一个名为search()的尾部递归函数，它有以下输入参数：

fruitName：String类型，要在数组中搜索的商品项。
fruits：String[]数据类型，代表商品数组。
index：Int类型，查找要在其上运行搜索的Array内的索引。

object demo {

  // @annotation.tailrec指示编译器添加与堆栈帧管理有关的任何优化，因为此函数是递归的。
  @annotation.tailrec
  def search(fruitName: String, fruits: Array[String], index: Int): Option[Boolean] = {
    if(fruits.length == index) {  //  对search函数的退出调用，因为我们已经遍历了Array中的所有元素
      None
    } else if(fruits(index) == fruitName) { // 将退出search函数，因为已经在Array中找到了搜索项
      Some(true)
    } else {
      val nextIndex = index + 1             // 将当前索引增加1
      search(fruitName, fruits, nextIndex)  // 递归调用search函数
    }
  }

  def main(args: Array[String]): Unit = {
    // 首先定义一个String类型的Array来保存一些商品
    val arrayDonuts = Array("苹果", "草莓", "水晶西瓜", "葡萄干")

    // 调用尾递归函数
    val found = search("苹果", arrayDonuts, 0)
    println(s"发现苹果 = $found")

    val notFound = search("巧克力", arrayDonuts, 0)
    println(s"发现巧克力 = $notFound")
  }
}

执行上面的代码，输出结果如下：

发现苹果 = Some(true)
发现巧克力 = None

调用尾部递归函数与调用任何其他函数没有太大区别，只需通过函数名调用该函数，并向其传递相应的参数。

尾递归函数将有助于防止调用堆栈中的溢出，因为循环结构的计算在每一步都发生。

在scala.util.control.TailCalls._包中，Scala为尾部递归提供了实用程序。利用这些实用工具我们可以创建尾部递归函数。从前面的内容可知，尾部递归函数将有助于防止调用堆栈中的溢出，因为循环构造的计算在每一步都发生。

如何使用scala.util.control.TailCalls._定义一个尾部递归函数？

当涉及到递归时，Scala在包scala.util.control.tailcalls._中提供了额外的实用程序。让我们继续，通过使用这些递归实用工具，重新编写上一步中的递归search()函数。

//import scala.util.control.TailCalls.TailRec
import scala.util.control.TailCalls._

object demo {

  def main(args: Array[String]): Unit = {
    // 首先定义一个String类型的Array来保存一些商品
    val arrayDonuts = Array("苹果", "草莓", "水晶西瓜", "葡萄干")

    // 调用对tailSearch的递归函数的语法略有不同，因为需要将调用封装在tailcall()中
    val tailFound = tailcall(tailSearch("苹果", arrayDonuts, 0))
    println(s"使用TailCall发现苹果 = ${tailFound.result}") // 注意:返回值需要通过调用result来获取

    val tailNotFound = tailcall(tailSearch("巧克力", arrayDonuts, 0))
    println(s"使用TailCall发现巧克力 = ${tailNotFound.result}")
  }

  // 使用scala.util.control.tailcalls._包中的实用程序创建尾递归函数
  def tailSearch(donutName: String, donuts: Array[String], index: Int): TailRec[Option[Boolean]] = {
    if(donuts.length == index) {
      done(None) // 注意: done是从scala.util.control.TailCalls._中导入的
    } else if(donuts(index) == donutName) {
      done(Some(true))
    } else {
      val nextIndex = index + 1
      // 注意: tailcall是从scala.util.control.TailCalls._中导入的
      tailcall(tailSearch(donutName, donuts, nextIndex)) 
    }
  }
}

执行上面的代码，输出结果如下：

使用TailCall发现苹果 = Some(true)
使用TailCall发现巧克力 = None

trampoline tail recursive

假设有两个尾部递归函数F(A)和F(B)，并且F(A)调用F(B)，但反过来F(B)也调用F(A)。

那么F(A)被称为蹦床尾部递归函数，因为调用堆栈在F(A)和F(B)两个函数之间来回跳转—因此得名trampoline。

使用scala.util.control.TailCalls定义一个蹦床函数。

为了保持示例简单，我们将假设下面的notSweetDonut()函数将从其donutList参数中记录第一个甜甜圈。然后，它将把甜甜圈列表的尾巴传递回verySweetDonut()函数的tailcall(verySweetDonut(donutList.tail)) 函数verySweetDonut()将检查甜甜圈列表的头部，如果它没有找到一个甜甜甜圈，它将回调notSweetDonut()函数。在verySweetDonut()和nosweetdonut()函数之间来回跳转就是蹦床效应。

import scala.util.control.TailCalls.TailRec
import scala.util.control.TailCalls._

object demo {

  def verySweetFruit(fruitList: List[String]): TailRec[Boolean] = {
    println(s"verySweetFruit 函数: fruit list = $fruitList")
    if (fruitList.isEmpty) {
      println("verySweetFruit 函数: fruit list是空的, 返回 false")
      done(false)
    } else {
      if(Set(fruitList.head).subsetOf(Set("苹果","西瓜","草莓"))) {
        println(s"verySweetDonut 函数: 找到fruit list's head = ${fruitList.head}非常甜,返回true")
        done(true)
      } else {
        println(s"verySweetDonut 函数: fruit list's head = ${fruitList.head}不甜, 将 fruit list转发给notSweetDonut 函数")
        tailcall(notSweetFruit(fruitList))
      }
    }
  }

  def notSweetFruit(fruitList: List[String]): TailRec[Boolean] = {
    println(s"notSweetDonut函数: fruit list = $fruitList")
    if (fruitList.isEmpty) {
      println("notSweetDonut 函数: fruit list是空的, 返回 false")
      done(false)
    } else {
      println(s"notSweetDonut 函数: fruit list's head = ${fruitList.head}不甜, 将 fruit list's tail转发给verySweetDonut 函数")
      tailcall(verySweetFruit(fruitList.tail))
    }
  }

  def main(args: Array[String]): Unit = {
    // 只需使用scala.util.control.TailCalls._中的tailcall()函数，
    // 并传递给它verySweetDonut()函数，该函数接受一个String类型的甜甜圈列表。
    val fruitList: List[String] = List("南瓜", "东瓜", "西瓜", "倭瓜")
    val foundVerySweetDonut = tailcall(verySweetFruit(fruitList)).result
    println(s"找到了非常甜的水果 = $foundVerySweetDonut")
  }
}

执行以上代码，输出结果如下：

verySweetFruit 函数: fruit list = List(南瓜, 东瓜, 西瓜, 倭瓜)
verySweetDonut 函数: fruit list's head = 南瓜不甜, 将 fruit list转发给notSweetDonut 函数
notSweetDonut函数: fruit list = List(南瓜, 东瓜, 西瓜, 倭瓜)
notSweetDonut 函数: fruit list's head = 南瓜不甜, 将 fruit list's tail转发给verySweetDonut 函数
verySweetFruit 函数: fruit list = List(东瓜, 西瓜, 倭瓜)
verySweetDonut 函数: fruit list's head = 东瓜不甜, 将 fruit list转发给notSweetDonut 函数
notSweetDonut函数: fruit list = List(东瓜, 西瓜, 倭瓜)
notSweetDonut 函数: fruit list's head = 东瓜不甜, 将 fruit list's tail转发给verySweetDonut 函数
verySweetFruit 函数: fruit list = List(西瓜, 倭瓜)
verySweetDonut 函数: 找到fruit list's head = 西瓜非常甜,返回true
找到了非常甜的水果 = true

小白学苑

让大数据学习更简单

尾递归函数

trampoline tail recursive