它写出的程序像动态语言一样简洁，但事实上它确是严格意义上的静态语言。">Scala 就像一位武林中的集大成者，将过去几十年计算机语言发展历史中的精萃集于一身，化繁为简，为程序员们提供了一种新的选择。作者希望通过这个系列，可以为大家介绍 Scala 语言的特性，和 Scala 语言给我们带来的关于编程思想的新的思考。
在初学计算机编程时，我想大多数人的经历会和作者一样，学校为我们挑选一门语言，大多为 C 或 Java，先是基本的数据类型，然后是程序控制语句，条件判断，循环等，书上会教我们如何定义一个函数，会说程序就是一条一条的指令，告诉计算机该如何操作。同时，我们还会看到如何定义一个递归函数，用来计算阶乘或斐波那契数列。工作以后，其他的这些基础还在日复一日的使用，但递归却很少再被用到，以致我们很难再用递归的方式去解决问题了，为此，我们还有一个借口：递归性能差，使用循环效率高。事实真是这样的吗？我们为自己某种能力的丧失编织了一个美丽的谎言，直到越来越多的编程语言变得流行起来，使11545.html">我们有机会看到各种语言、各种风格写出的程序，才发现自己应该重新审视递归这一概念了。
为什么递归会受到忽视
为了回答这一问题，必须先说到编程范式。在所有的编程范式中，面向对象编程（Object-Oriented Programming）无疑是最大的赢家。看看网上的招聘启事，无一例外，会要求应聘者熟练掌握面向对象编程。但其实面向对象编程并不是一种严格意义上的编程范式，严格意义上的编程范式分为：命令式编程（Imperative Programming）、函数式编程（Functional Programming）和逻辑式编程（Logic Programming）。面向对象编程只是上述几种范式的一个交叉产物，更多的还是继承了命令式编程的基因。遗憾的是，在长期的教学过程中，只有命令式编程得到了强调，那就是程序员要告诉计算机应该怎么做，而不是告诉计算机做什么。而递归则通过灵巧的函数定义，告诉计算机做什么。因此在使用命令式编程思维的程序中，不得不说，这是现在多数程序采用的编程方式，递归出镜的几率很少，而在函数式编程中，大家可以随处见到递归的方式。下面，我们就通过实例，为大家展示递归如何作为一种普遍方式，来解决编程问题的。
一组简单的例子
如何为一组整数数列求和？按照通常命令式编程的思维，我们会采用循环，依次遍历列表中的每个元素进行累加，最终给出求和结果。这样的程序不难写，稍微具备一点编程经验的人在一分钟之内就能写出来。这次我们换个思维，如何用递归的方式求和？为此，我们不妨把问题简化一点，假设数列包含 N 个数，如果我们已经知道了后续 N – 1 个数的和，那么整个数列的和即为第一个数加上后续 N – 1 个数的和，依此类推，我们可以以同样的方式为 N – 1 个数继续求和，直到数列为空，显然，空数列的和为零。听起来复杂，事实上我们可以用一句话来总结：一个数列的和即为数列中的第一个数加上由后续数字组成的数列的和。现在，让我们用 Scala 语言把这个想法表达出来。
清单 1. 数列求和
//xs.head 返回列表里的头元素，即第一个元素 //xs.tail 返回除头元素外的剩余元素组成的列表 def sum(xs: List[Int]): Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail)
大家可以看到，我们只使用一行程序，就将上面求和的方法表达出来了，而且这一行程序看上去简单易懂。尽量少写代码，这也是 Scala 语言的设计哲学之一，较少的代码量意味着写起来更加容易，读起来更加易懂，同时代码出错的概率也会降低。同样的程序，使用 Scala 语言写出的代码量通常会比 Java 少一半甚至更多。
上述这个数列求和的例子并不是特别的，它代表了递归对于列表的一种普遍的处理方式，即对一个列表的操作，可转化为对第一个元素，及剩余列表的相同操作。比如我们可以用同样的方式求一个数列中的最大值。我们假设已经知道了除第一个元素外剩余数列的最大值，那么整个数列的最大值即为第一个元素和剩余数列最大值中的大者。这里需要注意的是对于一个空数列求最大值是没有意义的，所以我们需要向外抛出一个异常。当数列只包含一个元素时，最大值就为这个元素本身，这种情况是我们这个递归的边界条件。一个递归算法，必须要有这样一个边界条件，否则会一直递归下去，形成死循环。
清单 2. 求最大值
def max(xs: List[Int]): Int = { if (xs.isEmpty) throw new java.util.NoSuchElementException if (xs.size == 1) xs.head else if (xs.head > max(xs.tail)) xs.head else max(xs.tail) }
同样的方式，我们也可以求一个数列中的最小值，作为一个练习，读者可下去自行实现。
让我们再看一个例子：如何反转一个字符串？比如给定一个字符串"abcd"，经过反转之后变为 "dcba"。同样的，我们可以做一个大胆的假设，假设后续字符串已经反转过来，那么接上第一个字符，整个字符串就反转过来了。对于一个只有一个字符的字符串，不需要反转，这是我们这个递归算法的边界条件。程序实现如下：
清单 3. 反转字符串
def reverse(xs: String): String = if (xs.length == 1) xs else reverse(xs.tail) + xs.head
最后一个例子是经典的快速排序，读者可能会觉得这个例子算不上简单，但是我们会看到，使用递归的方式，再加上 Scala 简洁的语言特性，我们只需要短短几行程序，就可以实现快速排序算法。快速排序算法的核心思想是：在一个无序列表中选择一个值，根据该值将列表分为两部分，比该值小的那一部分排在前面，比该值大的部分排在后面。对于这两部分各自使用同样的方式进行排序，直到他们为空，显然，我们认为一个空的列表即为一个排好序的列表，这就是这个算法中的边界条件。为了方便起见，我们选择第一个元素作为将列表分为两部分的值。程序实现如下：
清单 4. 快速排序
def quickSort(xs: List[Int]): List[Int] = { if (xs.isEmpty) xs else quickSort(xs.filter(x=>x<xs.head)):::xs.head::quickSort(xs.filter(x=>x>xs.head)) }
当然，为了使程序更加简洁，作者在这里使用了列表中的一些方法：给列表增加一个元素，连接两个列表以及过滤一个列表，并在其中使用了 lambda 表达式。但这一切都使程序变得更符合算法的核心思想，更加易读。