您的位置 首页 > 数码极客

〔复杂的递归如何理解〕如何理解递归算法…

1.递归是什么?

定义:程序调用自身的编程技巧称为递归。它分为调用阶段和回退阶段,递归的回退顺序是它调用顺序的逆序。

递归使用的是选择结构:if/switch。而for,while,do while使用的是循环结构。

定义不明白不要紧,先思考以下表达式,要怎么写程序来计算呢?

1+2+3....+100=?

很多人第一反应使用for循环来解决:

或者神级程序猿使用最简洁而且高效的公式(推荐使用,开销最小,且一步到位):

递归代码如下:

通过初体验对比,不难发现以下递归有以下几个要点:

1.优点:使程序结构更清晰,更简洁,更容易让人理解。

2.缺点:使用递归调用时,是方法调用方法,如果过多的调用容易造成栈溢出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题,需要谨慎使用。对于互联网这种以速度和效率来维护用户量,不得以用递归时,可以把处理的数据放入缓存,或者直接使用迭代等方式来解决。

3.规律:递归要有出口,不然成了死循环。解出递归的要点在于求出n-1,求出了n-1才能求解出n,这点后文有讲解。

2.递归的执行过程:

前文对于递归的定义中说,递归分为调用阶段和回退阶段,递归的回退顺序是它调用顺序的逆序。为了理解执行过程,这里配合实例讲解。请思考如何写出它的递归代码:

n!=n*(n-1)*(n-2)...*3*2*1

这里给出数学表达式:

从表达式中可以明显的可以看出:1.递归有出口。2.递归是选择结构。递归代码也不难:

它的调用顺序是怎么样的呢?

当你传入5时,方法内会去调用方法factorial(4),然后又调用方法factorial(3)直到factorial(0)=1时开始返回,下面为更详细的图解:

调用阶段

回退阶段

图中红色箭头为调用阶段,绿色箭头为回退阶段。这就是递归的要点在于求出n-1,求出了n-1才能求解出n,它思想其实和数学中的归纳本质上是相同的。

3.汉诺塔游戏讲解

游戏规则:有三根柱子,最左边的一根柱子从下往上按照大小顺序摞着64片圆盘。需要你借助中间的柱子把左边的所有圆盘移动到最右边的柱子上。并且规定,下面圆盘始终要比上面的大,在三根柱子之间一次只能移动一个圆盘。求出最少移动的次数。

如果要把X柱上得3个圆盘移动到Z柱,步骤如下:

①把X柱最上面的小圆盘移动到Z柱。②再把X柱中间大的圆盘移动到Y柱。③把Z柱上最小的圆盘移动到Y柱上。

这三次操作如图所示:

再加上步骤④⑤⑥⑦,所以3个圆盘至少需要移动7次。如果移动6个圆盘时:

所以可以推出,当n个从x柱,经由y柱中转,移动到z柱(解出n层汉诺塔时),有:

当n=0时,

不用做任何操作

当n>0时,

首先,将n-1个盘子从x借助z移动到y

然后,将1个盘子从x移动到z

最后,将在中间y上的n-1个盘子借助x移动到z

为了解出n层汉诺塔,需要先使用n-1层汉诺塔的解法。

从推到过程中我们可以发现:解出递归的要点在于求出n-1,求出了n-1才能求解出n。此外,从数学角度也可以归纳出 0,1,3,7,15,63...表达式为:f(n)=2^n - 1。

现在,我们可以给出代码:

4.总结和展望

递归对于解决某些问题非常方便(比如递归读取文件路径),也易于理解。虽然用迭代不是不可以实现,只是同样为了解决某些特性问题,写出迭代的代码花费的时间和难度却比递归高。

前文提到,递归和数学中的归纳思想本质上是相同的,都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。

责任编辑: 鲁达

1.内容基于多重复合算法人工智能语言模型创作,旨在以深度学习研究为目的传播信息知识,内容观点与本网站无关,反馈举报请
2.仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证;
3.本站属于非营利性站点无毒无广告,请读者放心使用!

“复杂的递归如何理解,如何理解递归算法,双层递归如何理解,如何理解递归思想”边界阅读