递归算法的两个特点：
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算法学习视频，本文仅供个人学习使用，特此声明