递归思维
基本情况和递归步骤。
递归思维 是 CoddyKit 上的免费 Scala for Backend Engineering & Functional Programming 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Scala for Backend Engineering & Functional Programming 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。
本课时的部分内容尚未翻译，以英文显示。
What Recursion Means
Recursion is when a function calls itself to solve a smaller version of the same problem.
In Scala, recursion is a natural fit for functional programming because it lets you express loops without mutable variables.
Every recursive function needs two things: a way to stop, and a way to shrink the problem.
Base Case First
The base case is the simplest input the function can answer directly, with no further recursion.
Without a base case, the function would call itself forever and crash with a stack overflow.
Always design the base case before the recursive step.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}A First Recursive Function
Here is a complete program that sums the numbers from 1 to n.
The base case returns 0; the recursive case adds n to the sum of everything below it.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15Tracing the Calls
To understand recursion, expand the calls by hand.
sum(3) becomes 3 + sum(2), which becomes 3 + 2 + sum(1), then 3 + 2 + 1 + sum(0).
Only when sum(0) returns 0 does the chain collapse back into a single value: 6.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6Recursion on Lists
Lists are recursive by nature: a list is either empty (Nil) or a head followed by a smaller tail.
This shape maps directly onto recursive functions. The empty list is the base case; the head plus recursion on the tail is the recursive step.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}Pattern Matching the Tail
The :: pattern splits a non-empty list into its head and tail.
Each recursive call works on a strictly shorter list, guaranteeing progress toward Nil.
This is the canonical way to walk a list recursively in Scala.
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 10Two Recursive Calls
Some problems branch into more than one recursive call.
The classic example is Fibonacci, where each value depends on the two before it.
This naive version is simple but slow, because it recomputes the same values many times.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13The Stack Cost
Each recursive call adds a frame to the call stack, which must wait for the inner call to return.
For very deep recursion, this can exhaust the stack and throw a StackOverflowError.
Counting depth, not just size, helps you predict this risk.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorShrinking Toward the Base
The key invariant of recursion is that every call must move closer to the base case.
If the argument does not get smaller, or never reaches the stopping condition, the recursion never ends.
Check this before running anything.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}Recursion vs Loops
Imperative code uses while loops with mutable counters; functional code uses recursion with immutable values.
Both can express the same computations, but recursion describes the structure of the data more directly.
In Scala, you will often prefer recursion or higher-order functions over raw loops.
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)Designing a Recursive Solution
A reliable recipe: identify the base case, assume the recursive call already works on the smaller input, then combine the head with that result.
This leap of faith is the heart of recursive thinking. You trust the smaller call and only handle one step.
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9Quick Check
Test your understanding of recursive structure.
Recap
Recursion solves a problem by reducing it to a smaller instance of itself.
Every recursive function needs a base case to stop and a recursive step that shrinks the input toward that base.
Lists, with their Nil and head-tail shape, are an ideal playground for recursive thinking. Watch the stack depth on very large inputs.
常见问题解答
「递归思维」课时是免费的吗？
是的 — 「递归思维」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 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 反馈 — 无需本地设置。