有趣的Scala语言: 使用递归的方式去思考

在初学计算机编程时,我想大多数人的经历会和作者一样,学校为我们挑选一门语言,大多为 C 或 Java,先是基本的数据类型,然后是程序控制语句,条件判断,循环等,书上会教我们如何定义一个函数,会说程序就是一条一条的指令,告诉计算机该如何操 作。同时,我们还会看到如何定义一个递归函数,用来计算阶乘或斐波那契数列。工作以后,其他的这些基础还在日复一日的使用,但递归却很少再被用到,以致我 们很难再用递归的方式去解决问题了,为此,我们还有一个借口:递归性能差,使用循环效率高。事实真是这样的吗?我们为自己某种能力的丧失编织了一个美丽的 谎言,直到越来越多的编程语言变得流行起来,使我们有机会看到各种语言、各种风格写出的程序,才发现自己应该重新审视递归这一概念了。

为什么递归会受到忽视

为 了回答这一问题,必须先说到编程范式。在所有的编程范式中,面向对象编程(Object-Oriented Programming)无疑是最大的赢家。看看网上的招聘启事,无一例外,会要求应聘者熟练掌握面向对象编程。但其实面向对象编程并不是一种严格意义上 的编程范式,严格意义上的编程范式分为:命令式编程(Imperative Programming)、函数式编程(Functional Programming)和逻辑式编程(Logic Programming)。面向对象编程只是上述几种范式的一个交叉产物,更多的还是继承了命令式编程的基因。遗憾的是,在长期的教学过程中,只有命令式 编程得到了强调,那就是程序员要告诉计算机应该怎么做,而不是告诉计算机做什么。而递归则通过灵巧的函数定义,告诉计算机做什么。因此在使用命令式编程思 维的程序中,不得不说,这是现在多数程序采用的编程方式,递归出镜的几率很少,而在函数式编程中,大家可以随处见到递归的方式。下面,我们就通过实例,为 大家展示递归如何作为一种普遍方式,来解决编程问题的。

一组简单的例子

如何为一组整数数列求和?按照通常命令式编程的思 维,我们会采用循环,依次遍历列表中的每个元素进行累加,最终给出求和结果。这样的程序不难写,稍 微具备一点编程经验的人在一分钟之内就能写出来。这次我们换个思维,如何用递归的方式求和?为此,我们不妨把问题简化一点,假设数列包含 N 个数,如果我们已经知道了后续 N – 1 个数的和,那么整个数列的和即为第一个数加上后续 N – 1 个数的和,依此类推,我们可以以同样的方式为 N – 1 个数继续求和,直到数列为空,显然,空数列的和为零。听起来复杂,事实上我们可以用一句话来总结:一个数列的和即为数列中的第一个数加上由后续数字组成的 数列的和。现在,让我们用 Scala 语言把这个想法表达出来。

清单 1. 数列求和

  1. //xs.head 返回列表里的头元素,即第一个元素 
  2. //xs.tail 返回除头元素外的剩余元素组成的列表 
  3. def sum(xs: List[Int]): Int = 
  4.  if (xs.isEmpty) 0 else xs.head + sum(xs.tail) 

大家可以看到,我们只使用一行程序,就将上面求和的方法表达出来了,而且这一行程序看上去简单易懂。尽量少写代码,这也是 Scala 语言的设计哲学之一,较少的代码量意味着写起来更加容易,读起来更加易懂,同时代码出错的概率也会降低。同样的程序,使用 Scala 语言写出的代码量通常会比 Java 少一半甚至更多。

上述这个数列求和的例子并不是特别的,它代表了递归对于列表的一种普遍的处理方式,即对一个列表的操作,可转化为对第一个元素,及剩余列表的相同操 作。比如我们可以用同样的方式求一个数列中的最大值。我们假设已经知道了除第一个元素外剩余数列的最大值,那么整个数列的最大值即为第一个元素和剩余数列 最大值中的大者。这里需要注意的是对于一个空数列求最大值是没有意义的,所以我们需要向外抛出一个异常。当数列只包含一个元素时,最大值就为这个元素本 身,这种情况是我们这个递归的边界条件。一个递归算法,必须要有这样一个边界条件,否则会一直递归下去,形成死循环。

清单 2. 求最大值

  1. def max(xs: List[Int]): Int = { 
  2.    if (xs.isEmpty) 
  3.      throw new java.util.NoSuchElementException 
  4.    if (xs.size == 1) 
  5.      xs.head 
  6.    else 
  7.      if (xs.head > max(xs.tail)) xs.head else max(xs.tail) 
  8. }v 

同样的方式,我们也可以求一个数列中的最小值,作为一个练习,读者可下去自行实现。

让我们再看一个例子:如何反转一个字符串?比如给定一个字符串"abcd",经过反转之后变为 "dcba"。同样的,我们可以做一个大胆的假设,假设后续字符串已经反转过来,那么接上第一个字符,整个字符串就反转过来了。对于一个只有一个字符的字符串,不需要反转,这是我们这个递归算法的边界条件。程序实现如下:

清单 3. 反转字符串

  1. def reverse(xs: String): String = 
  2. if (xs.length == 1) xs else reverse(xs.tail) + xs.head 

最后一个例子是经典的快速排序,读者可能会觉得这个例子算不上简单,但是我们会看到,使用递归的方式,再加上 Scala 简洁的语言特性,我们只需要短短几行程序,就可以实现快速排序算法。 快速排序算法的核心思想是:在一个无序列表中选择一个值,根据该值将列表分为两部分,比该值小的那一部分排在前面,比该值大的部分排在后面。对于这两部分 各自使用同样的方式进行排序,直到他们为空,显然,我们认为一个空的列表即为一个排好序的列表,这就是这个算法中的边界条件。为了方便起见,我们选择第一 个元素作为将列表分为两部分的值。程序实现如下:

清单 4. 快速排序

  1. def quickSort(xs: List[Int]): List[Int] = { 
  2.    if (xs.isEmpty) xs 
  3.    else 
  4.      quickSort(xs.filter(x=>x<xs.head)):::xs.head::quickSort(xs.filter(x=>x>xs.head)) 

当然,为了使程序更加简洁,作者在这里使用了列表中的一些方法:给列表增加一个元素,连接两个列表以及过滤一个列表,并在其中使用了 lambda 表达式。但这一切都使程序变得更符合算法的核心思想,更加易读。

尾递归

从上面的例子中我们可以看到,使用递归方式写出的程序通常通俗易懂,这其实代表这两种编程范式的不同,命令式编程范式倾向于使用循环,告诉计算机怎 么做,而函数式编程范式则使用递归,告诉计算机做什么。习惯于命令式编程范式的程序员还有一个担忧:相比循环,递归不是存在效率问题吗?每一次递归调用, 都会分配一个新的函数栈,如果递归嵌套很深,容易出现栈溢出的问题。比如下面计算阶乘的递归程序:

清单 5. 递归求阶乘

  1. def factorial(n: Int): Int = 
  2. if (n == 0) 1 else n * factorial(n - 1) 

当递归调用 n – 1的阶乘时,由于需要保存前面的 n,必须分配一个新的函数栈,这样当 n很大时,函数栈将很快被耗尽。然而尾递归能帮我们解决这个问题,所谓尾递归是指在函数调用的最后一步,只调用该递归函数本身,此时,由于无需记住其他变量,当前的函数栈可以被重复使用。上面的程序只需稍微改造一下,既可以变成尾递归式的程序,在效率上,和循环是等价的。

清单 6. 尾递归求阶乘

  1. def factorial(n: Int): Int = { 
  2.    @tailrec 
  3.    def loop(acc: Int, n: Int): Int = 
  4.      if (n == 0) acc else loop(n * acc, n - 1) 
  5.   
  6.    loop(1, n) 

在上面的程序中,我们在阶乘函数内部定义了一个新的递归函数,该函数最后一步要么返回结果,要么调用该递归函数本身,所以这是一个尾递归函数。该函数多出一个变量 acc,每次递归调用都会更新该变量,直到递归边界条件满足时返回该值,即为最后的计算结果。这是一种通用的将非尾递归函数转化为尾递归函数的方法,大家可多加练习,掌握这一方法。对于尾递归,Scala 语言特别增加了一个注释 @tailrec,该注释可以确保程序员写出的程序是正确的尾递归程序,如果由于疏忽大意,写出的不是一个尾递归程序,则编译器会报告一个编译错误,提醒程序员修改自己的代码。

一道面试题

也许有的读者看了上面的例子后,还是感到不能信服:虽然使用递归会让程序变得简洁易懂,但我用循环也一样可以实现,大不了多几行代码而已,而且我还 不用知道什么尾递归,写出的程序就是效率最高的。那我们一起来看看下面这个问题:有趣的零钱兑换问题。题目大致如下:假设某国的货币有若干面值,现给一张 大面值的货币要兑换成零钱,问有多少种兑换方式。这个问题经常被各大公司作为一道面试题,不知难倒了多少同学,下面我给出该问题的递归解法,读者们可以试 试该问题的非递归解法,看看从程序的易读性,及代码数量上,两者会有多大差别。该问题的递归解法思路很简单:首先确定边界条件,如果要兑换的钱数为 0,那么返回 1,即只有一种兑换方法:没法兑换。这里要注意的是该问题计算所有的兑换方法,无法兑换也算一种方法。如果零钱种类为 0 或钱数小于 0,没有任何方式进行兑换,返回 0。我们可以把找零的方法分为两类:使用不包含第一枚硬币(零钱)所有的零钱进行找零,使用包含第一枚硬币(零钱)的所有零钱进行找零,两者之和即为所有 的找零方式。第一种找零方式总共有 countChange(money, coins.tail)种,第二种找零方式等价为对于 money – conins.head进行同样的兑换,则这种兑换方式有 countChange(money - coins.head, coins)种,两者之和即为所有的零钱兑换方式。

清单 7. 零钱兑换问题的递归解法

  1. def countChange(money: Int, coins: List[Int]): Int = { 
  2.   if (money == 0) 
  3.     1 
  4.   else if (coins.size == 0 || money < 0
  5.     0 
  6.   else 
  7.     countChange(money, coins.tail) + countChange(money - coins.head, coins) 

结束语

本文通过实例,和大家一起重新审视了递归在编程中的应用,使用递归的方式去编程代表了一种编程思想上的转变,程序员应该站在更高的抽象层次上,告诉 计算机做什么,而不是怎么做。递归作为一种处理问题的普遍方式,应该得到更广泛的应用。事实上,在 Haskell 语言中,不存在 while、for 等命令式编程语言中必不可少的循环控制语句,Haskell 强迫程序员使用递归等函数式编程的思维去解决问题。作者也鼓励大家以后碰到问题时,先考虑有没有好的递归的方式实现,看看是否会为我们关于编程的理解带来 新的思考。

原文链接:http://www.ibm.com/developerworks/cn/java/j-lo-funinscala1/

更多相关文章
  •  Detours 修改段属性漏洞   受影响的软件及系统 Detours3.0 和之前 版本   简介 这个问题将其定位为一个漏洞可能不太合适,更可能是 Detours 的一个 BUG ,但是因为该缺陷会造成漏洞利用变得容易,因此将其定义为漏洞.其主要问题就是Detours 在使用过程中会将之前的可 ...
  •   每一个高手在成长路上, 都需要与墙作充足的对抗. 要么你成功, 站在世界之颠, 然后尽情汲取到顶级的知识; 或者或被它打趴下, 成为芸芸众生中的一人, 然后对它习以为常. 我也不例外. 前不久, 我刚在我的服务器上自行架好了自己的 "梯子". 这正是从 "梯子&qu ...
  • handle  [ˈhændl]    处理
  • 题目思路:splay,区间反转. [cpp]  #include<stdio.h>  #include<stdlib.h>  #include<string.h>  #include<string>  #include<queue>  #i ...
  • 1.分区要求 1)/:必须有的 2)swap:可选,一般为物理内存的1.5倍,当物理内存大于16G,选择8-16G即可 3)/boot:用来存放内核文件,一般100~200M即可,内核文件不超过100M 划分了分区之后,再格式化,格式化的目的是为了创建文件系统(文件系统可以理解为:组织文件的一种机制 ...
  • 聚集索引表插入数据和删除数据的方式是怎样的  根据<SQLSERVER聚集索引与非聚集索引的再次研究(上)>里说的,聚集索引维护着创建第一个聚集索引时的第一个字段的顺序来排序 当插入记录的时候,或者重新组织索引的时候都会按照字段顺序来排序 今天来做一个实验来验证一下  --华丽的 先创建 ...
一周排行
  • VMWARE是自我学习过程中一个很好的工具 我们可以利用VMWare在局域网中新建一个独立的虚拟服务器,为局域网用户提供网络服务 或者想创建一个与网内其他机器相隔离的虚拟系统,进行特殊的调试工作 那么要想用好虚拟机, ...
  • 在一系列尝试之后,人人网CEO陈一舟正在考虑用游戏的方式来反哺移动社交领域的布局.近日,人人游戏CTO(首席技术官)顾雷对<第一财经日报>表示,人人网已将部分无线部门人员调往人人游戏事业部,而大量的游戏开 ...
  • ArcPad是安装在手持设备或者移动终端的一个外业ArcGIS产品,也就是说ArcPad是Esri的一款软件产品,而不是硬件设备哦.虽然不比ArcGIS Desktop功能复杂缤纷,但是对于野外作业.数据采集等工作来 ...
  • 在移动web应用中,由于没有类似chrome和firebug的调试工具,调试起来比在PC上相对麻烦一些,有时候只能反复进行修改比对,但使用weinre我们可以轻松做到远程调试的功能. 什么是weinre? 官方解释: ...
  • 最近一直在看<python源码剖析>,现在将自己的认识一步步记录下来,既方便大家分享讨论,共同进步,也方便我自己以后的回顾复习 对象是Python中非常重要的一个概念,需要明确的是在Python中任何事物 ...
  •             我们国家的每一个字都能追根溯源,我国的国名"中国"更是意义非凡,"中"在古时指皇室,是权力的顶峰,也有得到的意思,还有沟通的意思,当然最广泛的意思是最为 ...
  • 1.数据类型 和C语言基本一样. 有一个特别数据类型id,可以储存任何类型的对象,它是实现多态和动态绑定的基础. Objective-C 2.程序结构 Objective-C和C的程序结构一模一样,具体用法相同. 顺 ...
  • 时隔两年,两百元股重现江湖. 昨日大盘波澜不惊,但创业板个股却表现抢眼,两市第一高价股--神州泰岳延续近期强劲走势,早盘小幅低开后便快速上扬.临近午市收盘,神州泰岳一举突破两百元整数关口,最高涨到200.8元,成为两 ...
  • http://nhibernate.sourceforge.net/quickstart.htmlNHibernate快速指南   什么是NHibernate   NHibernate 是一个基于.Net 的针对关系 ...
  • 关系型数据库SQLite3,它是一个支持SQL轻量级的嵌入式数据库,在嵌入式操作上有很广泛的,WM采用的也是SQLite3关于过于.原理方面的东西在这篇文章里不会提到,但是如果你想能够快速的学会操作SQLite3,那 ...