递归是什么?

感觉在生活中经常听见递归这个词,这词到底是什么意思呢?

推荐  (0) | 30人关注关注
24个答案
43 0

递归就是在解释自身时用到自身。
【补充:以下作出的是计算机科学领域的解释】
举个栗子,我们常常可以看到n!定义为n!=1*2*3*...*n
但如果将其递归地定义,那么
n!=n*(n-1)! (n>0)
1 (n==0)
实际计算一下,比如5!=5*4!
=5*4*3!
=5*4*3*2!
=5*4*3*2*1!
=5*4*3*2*1*0!
=5*4*3*2*1*1
=120
在这个定义中定义n!这个运算时用到了n!这个概念本身,可以联想下循环论证,但每次递归,问题都从求n!变为了求(n-1)!。只有有限的自我指涉才是递归,所以递归需要边界条件,否则我们永远不知道问题的答案而只是将问题表现为不同的形式。在这个问题中,随着n不断减小,最终n将达到0——在此之前,我们不知道1!,2!,3!...n!,直到n=0,由阶乘的定义可以知道,0!=1,所以我们就可以开始回代。
1!=1*0!=1;
2!=2*1!=2;
......
5!=5*4!=120。
回代是递归的逆过程。在这一过程中递归是将问题缩小(从5!到4!到3!……)到最小(0!),而回代则是将问题由最小的问题向外扩张,从0!推出1!再推出2!……最终得到答案。
从阶乘的问题来看,似乎递归没有任何优势——这种表示方法十分复杂,不如采取一般的表示方法。但是另外一些问题,递归更为方便,或必须使用递归解决。
例:汉诺塔问题。你有3根针和n个盘子,这些盘子上有洞,从而插到针上。盘子有大有小,大的盘子必须叠在小的盘子上面。你总可以取出某根针上最上面的一个盘子,并将它移到另一根针的最上面。n个盘子都插在第一根针上,请找出方案使所有盘子移到第三根针上。

这一个问题没有常规解法。如果你理解了上面递归定义的阶乘,你应该可以解决这个问题。






我们为了将第一根针的n个盘子移动至第三根针,可以先将上面n-1个盘子视作一个整体移动至第二根针,然后将最大的一个盘子移到第三根针,再将第二根针上的n-1个盘子视作一个整体移动至第三根针即可。
怎样将n-1个盘子视作一个整体移动呢?对了!可以将n-2个盘子先移到第三根针,然后将第n-1个盘子移到第二根针,再将n-2个盘子视作整体移动到第二根针即可!
因此,我们的方法是假定m个盘子位于针a,我们要将其移动至针c,我们可以先将m-1个盘子移动至针b,将一个盘子移动至针c,再将针b上的m-1个盘子移动至针c。当然,这是一个递归过程。
这样我们从移动n个盘子,变成移动n-1个盘子,又变成移动n-2个盘子,这样递归下去,最终会只需要移动1个盘子——此时我们就可以直接移动了,这也就是这个问题的边界条件。随后我们通过回代,便可以得到移动盘子的方法。
看到这里,你是否对递归的方法有了一些理解了呢?

17 1

精英王子高中退学,独立开发者,独立博客作者,深度 Git...

2012-10-02 01:38

从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:“从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:"从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:……”

一男子因在微博造谣称自己因在微博造谣自己因在微博造谣称自己因在微博造谣称自己因在微博造谣称自己因在微博造谣称自己因在微博造谣称自己因在微博造谣称自己因在微博造谣而被拘留十五日而被拘留十五日而被拘留十五日而被拘留十五日而被拘留十五日而被拘留十五日而被拘留十五日而被拘留十五日

XX词典:
递归:见递归

11 2

sqybi计算机科学与工程专业本科生,口琴控,动漫迷

2012-09-27 15:55

GEB中对此有一段非常精妙的解释(中文翻译也巧妙至极),这里稍微复述一下。

比如我碰到了一个神,他说他叫造物神,可以满足我一个愿望。然后我就提出了一个愿望,说我想要他满足我更多的愿望。
他想了想,说这个愿望越级了,他不能决定,需要请示上一级的神。
然后一个新的神出现了,他说他也叫造物神。我问他,刚才那个神也叫造物神,为什么你也叫造物神呢?他说,刚才那个神的全名是,“造物神 物色的 神”。
听了我的愿望,这个新的造物神也表示愿望越级了,于是请示他上一级的神。
然后又一个“造物神”出现了……

故事大概是这样,其中神的命名为:
造 物 神
造 物 神 物色的 神
造 物 神 物色的 神 物色的 神
造物神 物色的 神 物色的 神 物色的 神
...

这就是递归,递归地分解“造物神”这个词。

2 0

DTSIo成长中的数学工作者

2012-10-01 12:44
支持者: yaodi dy._.

看卓里奇的数学分析里面似乎定义了相关的东西。比如说归纳集。当然归纳集的定义也是基于实数的加法结构的所以也不是最最proper的。严格定义递归的概念依赖于严格定义的正整数。似乎在集合论里面正整数是用基数定义的,然后我就不懂了。

1 0
支持者: yaodi

GNU = GNU's Not Unix

递归,就是直接或者间接使用自身函数
exp1:


exp 2:

个人以为,自己如果要写递归,需要掌握好几点:
1.出口, 一个函数不可能无穷递归,它必须是有限的,
那么,在什么情况下,是递归结束呢?比如上面那两个示例当输入值a==0时候结束。
但要考虑到可能本来就输入一个负的值,所以a<=0时退出
2.普适性,递归函数最好让关系明朗,输入输出只局限在第N次递归和第N+1次递归上,铺的太开很容易自己把自己搞乱
3. 易懂,为啥要递归?它付出了效率为代价,来让人更好理解。递归更符合人的思维。一个函数就好像一个节点,在某个有限参数情况下,面对不同参数,应该做出什么反应?返回什么结果?这些思维要表达明白,不然的话,付出代价,却没有很多收获,亏大了

同时要注意:
任何递归都可以用非递归的手法来完成,虽然它易于理解,但是付出的是效率的代价。
(特指C/C++/Java/etc,据说lisp这个递归狂人很好很强大,可惜区区很弱搞不出真东西来),它比循环做同样事情要慢50%,所以不要滥用。

1 0
支持者: 春田花花花手镯

所以要想知道什么是递归,就要先知道什么是递归

1 0

如果不明白什么是递归,就读这个句子

1 0
支持者: Ezio.Auditore

lambda 运算基础上的 Y 演算子(很坑!) 用 Y 演算子来解释递归的好处是,你只要接受 lambda 和 应用序就好。

1 0
支持者: yaodi

其实递归不算是一种算法,本质是在编写程序时,用到了函数或过程,在解释时在其中调用本身,例如:
(PASCAL 使用者,以下伪代码,明白意思就行)
{程序写的很拙,看懂内涵就行}
—procedure dfs(i,j,sum:integer);
— begin
— if i=n then
— begin
— if sum>ans then ans:=sum;
— exit;
— end;
dfs(i+1,j,sum+a[i+1,j]);
— dfs(i+1,j+1,sum+a[i+1,j+1]);
— end;
数字三角形深搜,不带动规,其中过程dfs中用到了dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);
此乃递归;
再直观点说 楼上的“从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:“从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:"从前有座山.山里有座庙.庙里有个老和尚和小和尚.老和尚对小和尚说:……”这玩意儿就挺好,当老和尚不再继续讲了,上一个老和尚的故事也结束了,前一个的也结束了,直到返回第一个,一切over。
当然 还有一个很重要的,那就是结束条件,如以上程序结束条件就是搜到最后一层,exit退出,如果没这句话,就是传说中的死递归(死地鬼?) 说到了死递归,就不得不说一个抽象的东西——系统栈,一般WIN系统栈大约是8MB,每到一次递归,如果无法结束,则压入系统栈中,准备下一次递归,如此往复循环……直到满足结束条件,便依次出栈(栈的特点不是FIFO吗?)所以说,这也给了我们一个启示:千万表在递归中写数组,否则很小数据就会爆掉。
那么,形象说,咋结束递归呢?——从前有座山,山上有座庙,庙里有个老和尚和小和尚.老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,都挂了。

1 0
支持者: 呆头鹅

简单点的,你肯定听说过:

从前有座山,山里有座庙,庙里有个老和尚在给小和尚说故事,这个故事是这样说的:{
从前有座山,山里有座庙,庙里有个老和尚在给小和尚说故事,这个故事是这样说的:{
从前有座山,山里有座庙,庙里有个老和尚在给小和尚说故事,这个故事是这样说的:{
从前有座山,山里有座庙,庙里有个老和尚在给小和尚说故事,这个故事是这样说的:{
从前有座山,山里有座庙,庙里有个老和尚在给小和尚说故事,这个故事是这样说的:{

以下继续嵌套N次

}
}
}
}
}

0 0

楼上的为什么都没有提递归需要有跳出循环的条件的....

0 0

内含子-intron生物化学与分子生物学博士

2012-10-16 03:10

电脑盲说个简单的:比如你有一堆苹果和橙子,排好队,如果最左边是苹果,就吃掉,然后剩下的最左边如果还是苹果,就再吃掉。。。直到最左边是橙子的时候结束。over了。

0 0

Def Fn = 老婆永远是对的;如有质疑,请复述本句。
Text = 老婆是错的是错的是错的是错的是错的是错的是错的是错的。
Rs = Fn ( Text )
? Rs

模拟上述函数
【老婆是错的是错的是错的是错的是错的是错的是错的】是错的?不知道前面说什么,把前面括号里的代回Fn里去;
【老婆是错的是错的是错的是错的是错的是错的】是错的?不知所云,继续打包代回Fn里去;
【老婆是错的是错的是错的是错的是错的】是错的?还是不知道,继续……
……
最终……老婆是错的?根据函数Fn的定义,老婆永远是对的,所以【老婆是错的】的解当然是【错】啦,然后开始回代。
【老婆是错的】(错)是错的吗?负负得正,答案是【对】,继续回代……
【老婆是错的是错的】(对)是错的吗?对是错的吗?显示此解为【错】,继续回代;
……
【老婆是错的是错的是错的是错的是错的是错的是错的】是错的?我都晕了,经过很久的计算转化为:【错】是【错】的吗?显然最终Rs=【对】。

上述就是我对递归的理解。
我是学Basic的,一个函数(Function)或过程(Sub)中出现直接或间接引用自身的情况就叫递归。
经典的形式是:函数F要解决A(n)问题,但由于条件不足,先在函数F内部把他转换为解决A(n-1)问题代回函数F,在其中再如上转换为A(n-2)问题……一直循环直到A(0),A(0)这个问题可以直接解决,于是回答A(1)的问题,回答A(2)的问题……直到回答A(n)的问题,并最终返还函数F的结果。

0 0

大家都是从程序方面入手,我来换一个角度,从数学上简要说一说。
之前做递归程序的时候,写过这么一篇分析博文,粘过来,错的地方还望大家指正。
如何利用数学归纳法理解编程中的递归问题?

今天在看ANSI COMMON LISP中看到了列表中递归的一部分内容。书中说,递归不需要想清楚整个递归展开调用过程,而是分析清楚所有可能的情况即可。面对一个简单的递归,如下,是求一个列表长的函数
(defun len (lst)

(if (null lst)
0
(+ (len (cdr lst)) 1)))
这个的理解方法如下:
1.列表长度为0时,函数正确返回0。
2.假设当列表长度为n时,函数正确返回n。那么当列表长度为n+1时,根据函数定义可以知道,函数为返回列表n的长度加上1,这个时候,可以证明在n+1的情况下也成立。
所以,这个函数定义是正确的。
对于上面的内容,应该是很明白的,而且这应该就是明明白白的数学归纳法。
但是,接下来的问题是,如果不是简单的关于自然数的递归问题,而是树的问题,又应该怎么利用数学归纳法理解呢?应该把握什么是假设量、递增量?
如下面这一个树的复制的简单的递归函数:
(defun copy-our-tree (tr)
(if (atom tr)
tr
(cons (our-copy-tree (car tr))
(our-copy-tree (cdr tr)))))
自己在网上搜了一会儿,没有找到很清晰的答案,便开始四处求助,后面自己想了一个解决方案。不对的地方还希望大家多多包涵。
仔细一想,还是没有学好离散数学导致的问题。这个地方,应该是要使用强归纳。之前的那个长度求法是使用的最简单的归纳法,高中就学了。
所谓强归纳即使说:
1.先验证基本情况成立
比如k=0时成立
2.假设
k<=n时成立
3.归纳证明
利用k<=n时成立的条件来推导出k=n+1时也成立
这样就证明了问题。
这样让我们回到这个复制树的代码上来:
1.基本情况
当tr是一个原子时情况成立。
当tr是一个单节点单元(single cons)的时候情况也成立。
2.假设
假设,这个函数定义适用于所有的含有1<k<=n个单节点单元的列表(任意结构的树)。这里可以把k看做是形成的二叉树的基本节点的数目。
3.归纳证明
当列表含有n+1个单节点单元的时候,根据函数定义,这个时候执行的操作应该是这句话
(cons (our-copy-tree (car tr)) (our-copy-tree (cdr tr)))
我们知道(car tr)所得到的结果要么是一个原子,要么是一个单节点单元数<=n的列表(因为是从n+1单节点列表中分出来的),那么根据假设(our-copy-tree (car tr))能够完成任务,复制出一棵树,同理第二个参数也能够完成任务。最后,cons把这两部分衔接起来,形成一个新的树。
这个新的复制的树是否和原来的n+1单节点树结构一致呢?答案是肯定的。我们可以这样看,我们相当于把原来的那一颗树减成了两部分,前一部分交给第一个参数由它复制实现,后一部分交给第二个参数由它复制实现,再由cons粘贴得到重新粘合起来,就得到了和之前一模一样的复制结构。我举一个简单的例子大家就明白了:
比如((a b) c d)
按照树结构来说应该是这样的(图是我自己手画的,比较粗糙,大家见谅)(our-copy-tree (car tr)) 完成了复制左边a b结构的任务, (our-copy-tree (cdr tr))完成了复制右边c d的任务,而cons则制造了上面的那个空白块,把左右两部分链接起来,大家看,是不是两个结构完全一样?
这样就得以证明。

0 0

举两个最常见的递归的例子:

1. 计算机软件中对“树”的定义。

2. 数学中对行列式运算的定义。

具体的说来,递归定义就是一个定义用到了它自己。比如我们要定义一个函数f(x),我们不是写出类似于 :
"f(x) = ....x....x....x...x"这种的表达式,而是会有 “f(x) = x...x..f(x)...x”这种,当然这只是一个比方,具体的情况可能会比较复杂。

通常,递归定义的事物都有一个“边界”情况。比如,“树”的边界情况是一个节点,行列式的边界情况是2X2的行列式。

再具体的请楼主百度wiki。。。

0 0

TA喜欢TA TA喜欢TATA喜欢TA TA喜欢TATA喜欢TA TA喜欢TATA喜欢TA TA喜欢TA……

0 1

珠峰冰雪脑壳上打孔的

2012-10-16 23:50

我明白了:就是——儿子的 儿子的 儿子的 儿子的。。。。。的儿子!
或者: 父亲的 父亲的 父亲的 父亲的。。。。。的父亲!

0 1

额,三体2里的猜疑链貌似有异曲同工之妙,按贴中解释的话,应该属于回代?

汉诺塔以前在文曲星上玩的high到不行,个人建议初玩者从两个开始一个一个的增加难度。

0 1

汉诺塔那个用递归解决太经典了...

4 6

天马小loli文字游戏小组管理员

2012-09-27 14:23

意思是递归.

这就是递归.

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区