递归是编程中一个相对难以理解但是却又很重要的概念. 对于从命令式语言开始学习编程的程序员天生对此有理解缺陷, 而对于从类似C++这种对函数式编程范式不友好的语言开始学习编程的程序员就更加如此了.(比如我自己) 碰巧(其实不巧)最近在读这本书(这本书国内没有引进, 网上只有巨贵的亚马逊卖的原版, 我读的是网上的中文版), Paul Graham在书中讲述的如何写递归函数的部分, 让我印象深刻. 因为原书是讲Lisp的, 当然这个部分也是用Lisp作为例子描述的, 考虑到国内会看这本书的人太少, 能看懂Lisp的就更不多了, 我这里根据自己的理解, 重新整理一下. 最重要的是, 书中原来的例子太少, 太简单, 我自己提供了一些额外的, 并且更加复杂的例子. 以期对问题能有更好的理解.
什么是递归
迭代的是人,递归的是神
–L. Peter Deutsch
简单的定义: “当函数直接或者间接调用自己时,则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归并不直观, 也不符合我们的思维习惯, 相对于递归, 我们更加容易理解迭代. 因为我们日常生活中的思维方式就是一步接一步的, 并且能够理解一件事情做了N遍这个概念. 而我们日常生活中几乎不会有递归思维的出现.
举个简单的例子, 即在C/C++中计算一个字符串的长度. 下面是传统的方式, 我们一般都这样通过迭代来计算长度, 也很好理解.
size_t length(const char *str) { size_t length = 0; while (*str != 0) { ++length; ++str; } return length; }
而事实上, 我们也可以通过递归来完成这样的任务.
size_t length(const char *str) { if (*str == 0) { return 0; } return length(++str) + 1; }
只不过, 我们都不这么做罢了, 虽然这样的实现有的时候可能代码更短, 但是很明显, 从思维上来说更加难以理解一些. 当然, 我是说假如你不是习惯于函数式语言的话. 这个例子相对简单, 稍微看一下还是能明白吧.
迭代的算法可以这样描述: 从第一个字符开始判断字符串的每一个字符, 当该字符不为0的时候, 该字符串的长度加一.
递归的算法可以这样描述: 当前字符串的长度等于当前字符串除了首字符后, 剩下的字符串长度+1.
作为这么简单的例子, 两种算法其实大同小异, 虽然我们习惯迭代, 但是, 也能看到, 递归的算法无论是从描述上还是实际实现上, 并不比迭代要麻烦.
理解递归
在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证. 比如, 另外一个常见的例子是阶乘的计算. 阶乘的定义: “一个正整数的阶乘(英语:factorial)是所有小于或等于该数的正整数的积,并且0的阶乘为1。” 以下是Ruby的实现:
def factorial(n) if n <= 1 then return 1 else return n * factorial(n - 1) end end
我们怎么判断这个阶乘的递归计算是否是正确的呢? 先别说测试, 我说我们读代码的时候怎么判断呢?
回溯的思考方式是这么验证的, 比如当n = 4时, 那么factoria(4)
等于4
* factoria(3)
, 而factoria(3)
等于3
* factoria(2)
,factoria(2)
等于2
* factoria(1)
, 等于2 * 1
, 所以factoria(4)
等于4
* 3 * 2 * 1
. 这个结果正好等于阶乘4的迭代定义.
用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解.
Paul Graham提到一种方法, 给我很大启发, 该方法如下:
- 当n=0, 1的时候, 结果正确.
- 假设函数对于n是正确的, 函数对n+1结果也正确.
如果这两点是成立的,我们知道这个函数对于所有可能的n都是正确的。
这种方法很像数学归纳法, 也是递归正确的思考方式, 事实上, 阶乘的递归表达方式就是1!=1,n!=(n-1)!×n
(见wiki).
当程序实现符合算法描述的时候, 程序自然对了, 假如还不对, 那是算法本身错了…… 相对来说, n,n+1的情况为通用情况, 虽然比较复杂, 但是还能理解, 最重要的, 也是最容易被新手忽略的问题在于第1点, 也就是基本用例(base case)要对. 比如, 上例中, 我们去掉if
n <= 1
的判断后, 代码会进入死循环, 永远不会结束.
使用递归
既然递归比迭代要难以理解, 为啥我们还需要递归呢? 从上面的例子来看, 自然意义不大, 但是很多东西的确用递归思维会更加简单……
经典的例子就是斐波那契数列, 在数学上, 斐波那契数列就是用递归来定义的:
·F0 = 0
·F1 = 1
·Fn = Fn – 1 + Fn – 2
有了递归的算法, 用程序实现实在再简单不过了:
def fibonacci(n) if n == 0 then return 0 elsif n == 1 then return 1 else return fibonacci(n - 1) + fibonacci(n - 2) end end
改为用迭代实现呢? 你可以试试.
上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写, 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?
Paul Graham提到, 你只需要做两件事情:
- 你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
- 你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.
这个过程还是数学归纳法的方法, 只不过和上面提到的一个是验证, 一个是证明.
现在我们用这个方法来寻找汉诺塔这个游戏的解决方法.(这其实是数学家发明的游戏)
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
1.每次只能移动一个圆盘.
2.大盘不能叠在小盘上面.
这个游戏在只有3个盘的时候玩起来较为简单, 盘越多, 就越难, 玩进去后, 你就会进入一种不停的通过回溯来推导下一步该干什么的状态, 这是比较难的. 我记得第一次碰到这个游戏好像是在大航海时代某一代游戏里面, 当时就觉得挺有意思的. 推荐大家都实际的玩一下这个游戏, 试试你脑袋能想清楚几个盘的情况.
现在我们来应用Paul Graham的方法思考这个游戏.
一般情况:
当有N个圆盘在A上, 我们已经找到办法将其移到C杠上了, 我们怎么移动N+1个圆盘到C杠上呢? 很简单, 我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上, 然后再把第N+1个圆盘(最后一个)移动到C上, 再用同样的方法将在B杠上的N个圆盘移动到C上. 问题解决.
基本用例:
当有1个圆盘在A上, 我们直接把圆盘移动到C上即可.
算法描述大概就是上面这样了, 其实也可以看作思维的过程, 相对来说还是比较自然的. 下面是Ruby解:
def hanoi(n, from, to, other) if n == 1 then puts from + ' -> ' + to else hanoi(n-1, from, other, to) hanoi(1, from, to, other) hanoi(n-1, other, to, from) end end
当n=3时的输出:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
上述代码中, from, to, other的作用其实也就是提供一个杆子的替代符, 在n=1时, 其实也就相当于直接移动. 看起来这么复杂的问题, 其实用递归这么容易, 没有想到吧. 要是想用迭代来解决这个问题呢? 还是你自己试试吧, 你试的越多, 就能越体会到递归的好处.
递归的问题
当然, 这个世界上没有啥时万能的, 递归也不例外, 首先递归并不一定适用所有情况, 很多情况用迭代远远比用递归好了解, 其次, 相对来说, 递归的效率往往要低于迭代的实现, 同时, 内存好用也会更大, 虽然这个时候可以用尾递归来优化, 但是尾递归并不是一定能简单做到.
参考
writenby 九天雁翎(www.jtianling.com)
相关推荐
理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。 使用递归函数需要注意防止栈溢出。 在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧...
第五章 函数与应用5.6递归思想和递归函数正确答案:B你选对了如果递归函数没有递归结束的语句,将会导致无穷递归,从而执行时出现“死循环”正确答案:2 3 6如下
Oracle 递归函数介绍
由原始递归函数经过合成或原始递归得到的函数仍是原始递归函数.
省市县递归函数
在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法.在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分. 18117的数字和为:1+8+1+1+7=18....
简单的递归函数示意图-PDF可编辑格式,方便自己可视化了解递归函数每个步骤的状态
C语言递归函数设计,如何使用递归函数进行算法计算,这样可以提高程序的质量
递归函数例子8个数据结构 递归函数例子8个
演示了如何把低效率的递归函数转换成非递归的函数并完成相同的计算。
利用递归函数调用方式,将所输入的5个字符,以相反顺序打印出来。
根据题目要求使用递归函数,根据题目给定的数学算式,求出Succ(n)的值。可以在每一次调用递归函数时增加一个计数器,用来计算调用了多少次函数,最后输出Succ(n)的值和调用递归函数次数的值。
C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算...
c++递归函数基本代码.zip
我的程序在国外的SREVER上,自己编的程序存放到哪,我很难记清。 所以编了一个简单的目录递归函数,查看我的程序,很方便的php文件
在C++中用函数递归调用的方法实现辗转相除法求两个整数的最大公因子。
代码实例,主要是介绍基本递归的实现,函数的调用等。
使用环境:需要先安装PyCharm(请自己百度下载安装),以及然后官网上下载Python 2.7版本,以及Python 3.7版本后,安装在自己的电脑上。 使用步骤: ...目的:帮助理解递归函数在Python中的具体使用。
⼀个递归函数必定能改写为利⽤栈实现的⾮递归函数,反之,⼀个利⽤栈实现的⾮递归函数可以改写为递归 函数。需要注意的是递归函数递归层次的深度决定所需存储量的⼤⼩。 3) 分析递归算法的⼯具是递归树,从递归树上...
递归函数C语言 递归函数是指在函数的定义中调用自身的一种函数。递归函数在解决一些问题时非常有用,因为它可以将问题分解成更小的子问题,然后使用这些子问题的解来解决原始问题。 在C语言中,递归函数是一种特殊的...