递归
你是否经常听到身边的程序员说一些高大上的专业术语呢,那递归就一定是其中的一个,这里我们就来讨论下什么是递归。
如果你去查一些专业解释递归的程序书籍,就一定会看到书中经常会使用阶乘来举例。之所以使用阶乘,是因为它能最清楚的表达递归的核心概念。
我们首先解释下阶乘
5的阶乘 = 5! = 5 x 4 x 3 x 2 x 1 = ?
这里因为我们要算的是5!,数字还比较小,所以直接计算是比较快捷的,但是如果要计算100!呢,这个计算的过程是非常机械的
100的阶乘 = 100! = 100 x 99 x 98 x 97 x ...... x 1 = ?
我们应该把机械的工作交给计算机来处理,这样才能有时间发挥自己的创造才能。好了,现在有人要我计算100!是多少,让我用递归的思想来解释给你听整个过程是怎样的。
首先,我不肯能直接把答案给出来,但是如果有人能告诉我99!是多少的话,我就能计算出100!是多少。这一步非常关键
100!= 100 x 99!
于是我就去问另一个人99!是多少,暂且叫这个人为man0。显然man0也不可能直接告诉我答案,但是man0说,如果有人能告诉我98!是多少,它就能告诉我99!是多少
99! = 99 x 98!
于是man0找到man1,问他98!是多少。
man1找到man2,问他97!是多少。
......
设想这样下去,直到最后会怎样。manX被问到1!是多少,这个还需要问吗,1!等于1,这时manX就不需要再去问别人了,直接就可以把答案告诉问他问题的那个人。
然后,沿着这条问题链,反方向把答案传递回去,man5把答案告诉man4,man4把答案告诉man3,man3把答案告诉man2,man2把答案告诉man1,man1把答案告诉man0,man0把答案告诉我,我只要把man0告诉我的数值乘以100,就得到了100!。
这就是阶乘运算的整个过程,当我们站在一个全局的角度来看这个整个过程的话,会发现是非常复杂的,但是你在思考递归的时候不应该站在这样的角度,你应该把自己想象成man0或者man1,你只是其中的某一环,不需要去关注全局,这时候问题就会被简化了,仔细细考下。
上面的这个例子里,我们在计算100!的时候,用到了100个人,其中包括“我”、man0、man1......manX,这样来解释这个问题当然没问题,但是和递归的定义稍微有些出入。下面我们换一种方式来解释,不用100个人了,一个人就够。
怎么会原来需要100个人需要解决的问题,一个人就能解决了呢。
你是否看过“盗梦空间”呢,我们把100个人想象层100层梦境,当你想要计算100!的时候,然后你就带着99!是多少这个问题睡去,当第一层梦境醒来的时候,你就知道99!是多少了。第一层梦境会带着98!是多少这个问题睡去。就这样进入一层层的梦境,然后梦境会反方向的一层层醒来,最后当你真的醒来的时候,你就知道100!是多少了。是不是很神奇呢。
或许你会问,递归这个问题直接用乘法连续相乘就行了,何必用递归这么复杂的方法呢。
这里就要说到递归的一个优势,但你使用递归来思考的时候,只需要站在一个局部的角度来思考就行了,不回被整体的复杂度打乱思维。比如说我在计算100!的时候,只需要计算100乘以99!就可以了,具体99!是多少,就交给下一层梦境来解决。
就想上文中说的阶乘问题,我们可以用递归来解决,也可以用迭代(乘法连乘)来解决。迭代是一种非常直接的解决办法,和我们平时的思考方式完全一样,但是递归却不是,需要你去仔细的分析问题。有时候使用递归来解决问题,会让一个复杂的问题变得出奇的简单。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
3 4 评论
分享

全站热榜

正在热议