第11章——递归编程

使用解决子问题的方案解决一个问题，也就是递归，这种想法十分诱人。许多算法和 问题本质上都是递归的。一旦我们找到窍门，使用递归来设计解决方案就变得极富表现力 且直观。

11.1 一个简单的递归

ProgrammingRecursions/Factorial.scala

def factorial(number: Int): BigInt = {
  if (number == 0)
    1
  else
    number * factorial(number - 1)
}

运行结果

120

ProgrammingRecursions/Factorial.scala

println(factorial(5))

ProgrammingRecursions/Factorial.scala

println(factorial(10000))

运行结果

java.lang.StackOverflowError

11.2 尾调用优化（TCO）

ProgrammingRecursions/Mad.scala

def mad(parameter: Int): Int = {
  if (parameter == 0)
    throw new RuntimeException("Error")
  else
    1 * mad(parameter - 1)
}

mad(5)

运行结果

java.lang.RuntimeException: Error
	at Main$$anon$1.mad(mad.scala:3)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.mad(mad.scala:5)
	at Main$$anon$1.<init>(mad.scala:8)

ProgrammingRecursions/Mad2.scala

def mad(parameter: Int): Int = {
  if (parameter == 0)
    throw new RuntimeException("Error")
  else
    mad(parameter - 1)
}

mad(5)

运行结果

java.lang.RuntimeException: Error
	at Main$$anon$1.mad(mad2.scala:3)
	at Main$$anon$1.<init>(mad2.scala:8)

  private int mad(int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmpne     15
       5: new           #14                 // class 
java/lang/RuntimeException
       8: dup
       9: ldc           #16                 // String Error
      11: invokespecial #20                 // Method 
java/lang/RuntimeException."<init>":(Ljava/lang/String;)V
      14: athrow
      15: iconst_1
      16: aload_0
      17: iload_1
      18: iconst_1
      19: isub
      20: invokespecial #22                 // Method mad:(I)I
      23: imul
      24: ireturn

  private int mad(int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmpne     15
       5: new           #14                 // class 
java/lang/RuntimeException
       8: dup
       9: ldc           #16                 // String Error
      11: invokespecial #20                 // Method 
java/lang/RuntimeException."<init>":(Ljava/lang/String;)V
      14: athrow
      15: iload_1
      16: iconst_1
      17: isub
      18: istore_1
      19: goto          0

ProgrammingRecursions/FactorialNoTCO.scala

@scala.annotation.tailrec
def factorial(number: Int): BigInt = {
  if (number == 0)
    1
  else
    number * factorial(number - 1)
}

println(factorial(10000))

运行结果

error: could not optimize @tailrec annotated method factorial: it contains
a recursive call not in tail position
    number * factorial(number - 1)
           ^
error found

ProgrammingRecursions/FactorialTCO.scala

@scala.annotation.tailrec
def factorial(fact: BigInt, number: Int): BigInt = {
  if (number == 0)
    fact
  else
    factorial(fact * number, number - 1)
}

println(factorial(1, 10000))

运行结果

284625968091705451890641321211986889014805140170279923079417999427441134000
...

11.3 蹦床调用

ProgrammingRecursions/Words.scala

import scala.io.Source._

def explore(count: Int, words: List[String]): Int =
  if (words.isEmpty)
    count
  else
    countPalindrome(count, words)

def countPalindrome(count: Int, words: List[String]): Int = {
  val firstWord = words.head

  if (firstWord.reverse == firstWord)
    explore(count + 1, words.tail)
  else
    explore(count, words.tail)
}

def callExplore(text: String): Unit = println(explore(0, text.split(" ").toList))

callExplore("dad mom and racecar")

try {
  val text =
    fromURL("https://en.wikipedia.org/wiki/Gettysburg_Address").mkString
  callExplore(text)
} catch {
  case ex: Throwable => println(ex)
}

运行结果

3
java.lang.StackOverflowError

ProgrammingRecursions/WordsTrampoline.scala

import scala.io.Source._
import scala.util.control.TailCalls._

def explore(count: Int, words: List[String]): TailRec[Int] =
  if (words.isEmpty)
    done(count)
  else
    tailcall(countPalindrome(count, words))

def countPalindrome(count: Int, words: List[String]): TailRec[Int] = {
  val firstWord = words.head

  if (firstWord.reverse == firstWord)
    tailcall(explore(count + 1, words.tail))
  else
    tailcall(explore(count, words.tail))
}

def callExplore(text: String): Unit =
  println(explore(0, text.split(" ").toList).result)

callExplore("dad mom and racecar")

try {
  val text =
    fromURL("https://en.wikipedia.org/wiki/Gettysburg_Address").mkString
  callExplore(text)
} catch {
  case ex: Throwable => println(ex)
}

运行结果

3
352