1.递归算法

1.递归算法

递归算法的两个特点：

1.调用自身  2.结束条件

判断下面4个函数哪个是正确的递归:

答案：1、 2是错误的，1缺少结束条件，2结束条件无法起作用。思考：3、 4有什么区别

 事实证明，3,4区别如下：这个是3

 

这个是4

 

 原因如下：因为前者是先输出再递归后者是先递归再输出，如下图，前者在原本的框内输出再创造一个新的框，后者是先创造新的框在到尽头再回来

 下面看一个实例

具体规则如上图描述

不妨先讨论简单情况：当n=3时，会经历以下过程：

1.小：A-->C                                                       

2.中：A-->B                                                       把中小这个整体从A到B

3.小：C-->B

———————————————————————————————————————————

4.大：A-->C                                                        把大从A到C

———————————————————————————————————————————

5.小：B-->A

6.中：B-->C                                                         把中小这个整体从B到C

7.小：A-->C

就是把最底下的大看作一个整体，把剩余的中和小看作一个整体，相当于把这个问题简化成

1.把中小这个整体从A到B

2.把大从A到C

3.把中小这个整体从B到C

把n改为一个未知量即可得到以下情况：

我们会发现，递归算法的本质就是把一个规模为n的问题简化为一个规模为n-1的同样的问题。 

则可以列出表达式

 算法实现如下：

个人心得：在递归算法中，列出表达式，然后直接码上去，问题就迎刃而解了，譬如wzoi.cc上有这样一个问题

 列出表达式：f(x)=f(x-1)+k

                       f(1)=a

代入即可

 

 这个是自己做的程序，因为wzoi.cc暂不支持python的测评，wzoj上面又还没有更新到这道题，故只测试了所给测试点数据，结果正确。若有差强人意之处，还望各位大佬指教。

部分图片参考自b站路飞学城python算法学习视频，本文仅供个人学习使用，特此声明