Scala for Backend Engineering & Functional Programming · 课时

递归基础

Q: 「递归基础」这节课中我会学到什么？

递归函数 你通过在浏览器中直接运行的动手代码来练习 Scala for Backend Engineering & Functional Programming，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

递归函数

递归基础 是 CoddyKit 上的免费 Scala for Backend Engineering & Functional Programming 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Scala for Backend Engineering & Functional Programming 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。

什么是递归

递归是指函数调用自身，以解决同一问题的规模更小的版本。递归非常适合函数式编程，可以用自引用定义替代许多循环。

两个必要部分

每个正确的递归函数都需要：

用于停止递归的基本情况。
朝基本情况推进的递归情况。

如果不存在可到达的基本情况，递归就会永远运行。

阶乘

经典示例：n! = n * (n-1)!，其中 0! = 1 是基本情况。

object Main {
  def factorial(n: Int): Int =
    if (n <= 1) 1
    else n * factorial(n - 1)

  def main(args: Array[String]): Unit = {
    println(factorial(5))
  }
}

跟踪调用过程

每次递归调用都会暂停，等待内部调用的结果。factorial(3) 展开为 3 * (2 * (1))。乘法会在调用返回时执行。

object Main {
  def factorial(n: Int): Int = {
    println(s"entering factorial($n)")
    if (n <= 1) 1 else n * factorial(n - 1)
  }

  def main(args: Array[String]): Unit = {
    println("result = " + factorial(3))
  }
}

列表求和

对列表进行递归：总和是头部元素加上尾部的总和，空列表的总和为零。

object Main {
  def sum(xs: List[Int]): Int = xs match {
    case Nil     => 0
    case h :: t  => h + sum(t)
  }

  def main(args: Array[String]): Unit = {
    println(sum(List(1, 2, 3, 4)))
  }
}

列表长度

使用相同的模式可以计算长度：空列表的长度为 0，否则就是 1 加上尾部的长度。

object Main {
  def length[A](xs: List[A]): Int = xs match {
    case Nil    => 0
    case _ :: t => 1 + length(t)
  }

  def main(args: Array[String]): Unit = {
    println(length(List("a", "b", "c")))
  }
}

调用栈

每个尚未完成的递归调用都会使用一个栈帧。深层递归会堆积许多栈帧。对于非常大的输入，这可能耗尽栈空间并抛出 StackOverflowError。

斐波那契数列

有些问题会分支为多个递归调用。斐波那契数列会调用自身两次，这种写法很优雅，但代价呈指数增长。

object Main {
  def fib(n: Int): Int =
    if (n < 2) n
    else fib(n - 1) + fib(n - 2)

  def main(args: Array[String]): Unit = {
    println(fib(10))
  }
}

反转列表

递归可以构建新结构：先反转尾部，再将头部追加到其后。

object Main {
  def reverse[A](xs: List[A]): List[A] = xs match {
    case Nil    => Nil
    case h :: t => reverse(t) :+ h
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3)))
  }
}

递归与迭代

循环会改变计数器；递归则以声明式方式表达问题。两者都有效。递归非常适合树形数据和分治算法，但对于大型线性输入，朴素递归可能导致栈溢出。

最大公约数

欧几里得算法天然适合递归，并且收敛很快。

object Main {
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(48, 18))
  }
}

快速检查

检验您的递归基础。

回顾

您学习了递归基础：

每个递归函数都需要基本情况和递归情况。
每个尚未完成的调用都会使用一个栈帧；深层递归可能导致栈溢出。
递归可以自然地表达列表和树算法。

接下来，您将使用 @tailrec 注解让递归具备栈安全性。

常见问题解答

「递归基础」课时是免费的吗？

是的 — 「递归基础」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Scala for Backend Engineering & Functional Programming 课程的其余内容，请升级到 CoddyKit PRO。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。

「递归基础」这节课中我会学到什么？

递归函数你通过在浏览器中直接运行的动手代码来练习 Scala for Backend Engineering & Functional Programming，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Scala for Backend Engineering & Functional Programming 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Scala for Backend Engineering & Functional Programming 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「递归基础」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Scala for Backend Engineering & Functional Programming 课中编写并运行代码吗？

能。每节 Scala for Backend Engineering & Functional Programming 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Scala for Backend Engineering & Functional Programming