【再谈递归】递归理解了,该如何去写程序

如果你理解了递归,那么你就成功了一半

递归分为两个部分,“递”和“归” 递归递归先递再归。

可能很多同学对递归还不了解,那我在这里来说一说:何为递归。

何为递归?

递归指的是在函数(方法)的定义中使用函数(方法)自身的方法。 举个例子: 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有 …

所以,递归的特点之一:函数自己调用自己

不过像上述“老和尚讲故事”的案例,通常称为 单程递归 (这个概念来自于 刘慈欣的《星际战争》第11章),所谓单程递归,就是没有返回的递归,也就是只有递,没有归。

如何理解递归

众所周知,在一个函数(方法)被调用时,会开辟一个新的空间,而在递归时,函数调用自己,也会新开一个空间,而每当新开的空间内函数调用完毕时,会将值返回给上一个空间,无限重复调用,直到找到基准为止(我对于内存空间的研究有限,可能说的不太对,不过也是为了便于大家的理解)

用递归写个斐波那契,大家都很好想像,不过用递归来写排序呢?快速排序可能还好点,如果是归并,给人的感觉就有点抽象了

快速排序
归并排序

要是每一次自行模拟的时候,都带进去,人不累死,脑子都得晕死。

所以,如何用好递归?

用好递归

前面说到,递归是有返回值的,所以,我们在写递归的时候,不妨设它是一个已经写好了的函数,我们只需要知道他返回的结果是多少不就可以了吗。

下面以斐波那契数列为例(万能的斐波那契,赐予我力量吧!)

调用fib(n-1)+fib(n-2)时,我们如果带进去算,会陷入循环中,循环到底回来的时候,还要记录返回值,对于计算机来说,有手就行,但对于我们普通人来说,特别绕(特别是当输入的n很大时),我们不妨假设已经知道它的返回值来运行,再进行调试,这样的话,便不会陷入头晕目眩的恶性循环。

  • 微信或QQ扫一扫

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

目录