“虽然自然辩证法这个理论是绝对正确的，但是我总感觉对解决实际问题的帮助不是很大。”小P对老C说道。两个人下了自然辩证法的课，向东2楼走去。一边走小P一边评论。
“呵呵，”老C笑道，“虽然我们平时分析问题都是在静态情况下分析和解决，但是，无论如何辩证法告诉我们这样有可能是不正确的。因为人类受智力限制，只能
在静止的，片面的角度去分析问题——如果一次考虑了太多的外界因素，使用运动的观点去看问题，反而会导致问题过于复杂以至于无法分析和解决。但是我们在解
决问题以后也不要忘记在实践中去检验我们的解决问题的方法，因为——辩证法告诉我们——我们的解法虽然在理论上成立，但前提——我们是在一个割裂的和静态
的环境中去考虑问题的——好像有可能是不恰当的。”
“哦？”小P点头，“就是说辩证法最重要的作用是……提醒我们请在实践中检查我们的理论……呵呵。”他骚骚一笑，“感觉辩证法的作用更像是一个错误分析理
论，用来告诉我们错误是怎样发生的以及为什么会发生这种错误，但是好像并不能非常有效的指导我们避免错误，因为依照这种理论去解决问题，好像就会陷入太多
的细节，需要考虑的因素太多，反而无法开始工作了……”
“呵呵，”老C笑道，“那么我们就先静态的、割裂的解决一个问题先。”说着两个人走进了教研室，他从角落里拉过来白板。“汉诺塔的故事你听说过吧？”老C问。
“嗯，这个题目我以前也做过，怎么？”小P问。
“那样更好，我就不用多费口舌了。”老C说道，“现在的问题是，请你求解一下解决这个问题，总共需要多少步。不要死记硬背以前记过的公式，我知道你以前做
过，我们需要从原理一步一步推导下去，这样才更有意义一些。”他拦住急于在白板上写写画画的小P，说道，“我们需要讲究一些方法，也是一般我们解决问题的
思路，现在我们就照这个思路来进行。”
“哦？按照什么样的思路？”小P问。
“我们可以这样想象一下，我们所有已经掌握的知识就像工具箱，一个一个排列在我们的右手；我们面对的问题也是一个一个的小箱子，排列在我们的左手。我们首
先要熟悉我们的工具箱，知道工具箱里面的工具是应对什么问题的，应当如何被使用——比如我们需要了解一个活动扳手是如何拧紧螺母的；然后我们左手的问题箱
子需要被分类，归结到我们可以依靠工具箱解决的一类与依靠我们目前的工具箱无法解决的一类——比如我们看到螺丝，就会想到用螺丝刀，而看到螺母，就会想到
用扳手，如果我们可以正确的对问题分类，对于可以使用工具箱中的工具解决的问题，那么从右手边的工具箱中拿出工具——解决问题就行了；然后我们需要在实践
中再检验一下我们解决问题的效果，根据反馈的信息再对问题进行进一步的细分种类，选择更加合适的工具——如此循环，直到问题被解决的程度可以被接受为止。
”老C开始长篇大论，“所以解决问题的过程实际是逆向思维的过程，一般来说逆向思维都带有尝试的性质，试的好不好，那要看你的个人经验和悟性。”
“那么对于无法使用工具箱解决的问题呢？”小P说道。
“呵呵，那就需要一些创造性的劳动了。”老C回答。“如果我们对已经有的工具的原理足够了解，我们就可以用这些工具来生产一些新的工具来解决新的问题。”
他吞了一口唾沫，“但是我们也需要对遇到的问题进行足够的了解——了解它的某些特质，使得我们制造工具的活动不会变得很盲目。”
“是吗？”小P问，“那么如何开始呢？”
“首先我们先简化问题，比如这个汉诺塔问题，我们可以先在3、5个碟子的情况下玩一玩，寻找一些规律。然后再考虑考虑此类问题如何被解决，通法是什么。”
他挠挠头，“呵呵，那么我们就开始吧。由于我智力有限，一时无法理解n个盘子的汉诺塔问题，我们就先从3个盘子开始好不？盘子3表示最大的，在最底下，盘
子1表示最小的，在最上面；同样我们也需要对杆子编号，最左面的叫1号，最右面的叫3号，你自己想想2号杆在什么地方……”
“……好啊好啊，那么我们就先来试试吧。”说着小P在白板上画了起来。
“呵呵，画的不好，像树枝穿便便……”小P谦虚道。
“……”老C一时无语。过了一阵子，老C止住恶心，问道，“你看看这几副图，有没有发现什么规律？”
“哦？什么意思？会有什么规律呢？”小P问。
“可能现在图太多了，让我们抽象一些，我来擦掉几副图。”老C说道，然后他在白板上将某些图擦去。
“唔……”小P盯着看了一会儿，说道，“好像是经过某些步数，将1号与2号盘子放到中间的杆子上，再将3号盘子放在最右边的3号杆子上，然后再经过某些步
数，将1号和2号在放到3号杆子上。”他想了想，道，“如果这样看的话，好像移动3个盘子的问题变为：将两个盘子移到第2个杆子，将3号盘子移到第3个杆
子，再将这两个盘子移到第3个杆子。”
“是的，的确是这样。”老C赞叹，“如果我用Tn表示从一个杆子移动n个盘子到另一个杆子——比如从1号移到3号杆，所需要的步数，那么我们会得到什么呢？”
“唔……”小P想了想，“好像是这样，先将上面的(n-1)个盘子移到……无论什么地——比如说2号杆吧……这将需要Tn-1步，将最底下的第n个盘子从1号杆移到3号，这需要1步，再将那(n-1)个盘子从帮忙的杆子上移到我们的3号杆，还是需要Tn-1步……这样我们得到Tn = Tn-1 + 1 +
Tn-1 = 2Tn-1 + 1。”
“嗯，的确是这样，但是还不算完。”老C说道，“你看，我们得到了一个递推的公式，但是……没有推导的终点……我们必须在某点结束推导。”他说，“因为n >= 0，所以我们需要在n = 0时结束推导，这样相当容易，因为T0 = 0……因为如果有0个盘子需要移动，我们什么都不用做，步数自然就是0了。”他继续说道，“这样我们就有了一组递推数列。”于是他在白板上写下了如下的公式。
T0 = 0
Tn = 2Tn-1 + 1
“看看，这样问题就变为将这个递推公式转变为通项公式了。”老C说道，“发挥你强悍的数学知识，解决这个问题吧！”然后他幸灾乐祸的躲到一边喝茶。
“切，这个算什么，小case啦！”小P嘴硬道，“这些东西我高中就会玩了。”于是他拿起一支笔，在白板上涂涂抹抹起来，“唔，这样……然后这样……不对不对……应当这样……嗯……”
没有理会小P的自言自语，老C慢慢的喝着茶水，跑去起点上看起了水文。
半个小时后……
“嗷！”小P突然喊道。
“干什么！你……”老C吓得从椅子上跳了起来。
“我知道怎么做了！”小P兴奋的说道。
“哦？”老C觉得这个小家伙还是比较强悍的，“你是怎么做的？这么快就做出来啦？”
“嘿嘿，”小P得意的说，“只要在两边同时处以2n就可以将问题转化为求一个队列的前n项和的问题。”说罢他指着白板上的一些演算。
Tn / 2n = 2Tn-1 / 2n + 2-n
Tn / 2n = Tn-1 / 2n－1 + 2-n
令Sn = Tn / 2n，则S0 = T0 / 20
= 0
那么原式可以转化为：
S0 = 0
Sn = Sn-1 + 2-n
这个是等比数列an = 2-n 数列前n项求和(n >= 1)。所以利用等比数列求和公式，
又Sn = Tn / 2n，所以
Tn = 2n * Sn = 2n(1 – 2-n)
= 2n – 1
所以
Tn = 2n – 1
“看就是这样求出来的。”小P得意的说道。
“呵呵，你是怎么想到要用等比数列求和的呢？”老C问。
“因为……我只知道等差数列和等比数列的求和公式，我总要把问题转化到我可以求解的范围内部啊，这样才可以求解。”小P说道。
“呵呵，你的想法很好啊，知道用已经掌握的工具去制造新的工具来解决问题，不错不错……但是美中不足的是在这一过程中充满了技巧和构造，对于编程人员来
说，他们是比较不喜欢技巧和构造的巧合的东西，因为这些比较难以编程实现。”老C打击了一下小P，“不过你还是很厉害啊，这样都可以想出来。”老C又补了
一颗糖。
“……”小P一时不知道该说些什么。
“好吧，现在我们使用超级无敌蛮力计算机来解决这个问题吧。”老C说道，“我们先使用计算机的无敌蛮力解算这个问题，然后我们来推导一些关于递归的常用公式，并总结一些常用的计算方法。”
“唔，好吧。”小P说道，“编写递归函数，这个我以前也学习过，一般就是分为两个部分。一个是递归结束条件，放在函数内部的前面，另外一部分是递归本身啦。”说着他打开电脑，新建立了一个工程，编写了一个极其简单的函数。
main.cpp
#include <iostream>
int Times (int n);
int main()
{
std::cout
<< "Please enter a number > 0: ";
int
n;
std::cin
>> n;
int
res = Times(n);
std::cout
<< "The result is: " << res << std::endl;
return
0;
}
int Times(int n)
{
if
(0 == n)
{
return
0;
}
return
2 * Times(n - 1) + 1;
}
写完后小P试着输入几个数字，并确认了他设计的函数是正确的。
“这样做有一种暴力美学……”老C评论，“但是为了更加深入的了解到递归本身，我们还需要再继续深入的讨论一些其他的相关问题。”说罢他在白板上写下一组公式。
anTn = bnTn-1 + Cn
“看，这个就是我们会遇到的某些递归问题的一种更一般的形式，其中an，bn和cn都是值随着n变化的系数，而Tn是我们希望求解的数列通项。”老C说道，“如果让我们一开始就求解这个东东，那么也太难了，我们先来解决一个更简化一些的问题——这也是我们解决问题时通常的思路——来找找灵感，看会带来一些思索的线索。”
T0 = α
Tn = Tn-1 + β + γn
“看，我们简化了这个问题，使得递推的增长项成为一个n的线性项，这样就可以大大简化刚才的问题。”老C道，“不要厌恶希腊字母，我相信你在数学书上看到
的希腊字母的次数绝对不会超过史诗级悬疑恐怖战争爱情巨作《伯罗奔尼撒战记》的原本……但是，虽然问题被简化了，但是像我这种智力水平底下的人，还是无法
理解的，所以我要试着代入几个n的值，看看究竟会有什么样子的规律。”说着他在白板上擦出一大片的空白，开始在上面写东西。
T0 = α
T1 = T0 + β + γ
T2 = T1 + β + 2γ = (T0
+ β + γ) +β + 2γ = α+ 2β
+ 3γ
T3 = T2 + β + 3γ = (T0
+ 2β + 3γ) +β + 3γ = α + 3β + 6γ
“看……”老C说道，“我们似乎可以发现，其实Tn可以被分解为3个数列的和。”说完，他在白板的醒目位置写下如下的式子。
T0 = α
Tn = αAn + βBn + γCn
“就是说我们认为，如果队列Tn可以表示为T0 =α; Tn =αAn + βBn + γCn 的形式，那么对于任意的α、β和γ，只要α、β、γ这3个参数的值被确定，那么Tn一定也可以被表示为T0 = α; Tn = Tn-1 + β + γn 的形式。”
“……的确是这样啊，你这样将问题反过来描述一下，有什么意义呢？”小P不解。
“呵呵，也就是说如果An、Bn、Cn的通项被确定和α、β、γ的值被确定，那么Tn就被确定；其中An、Bn、Cn是不变的数列，而α、β、γ是可以任意变化的参数，对应不同的α、β、γ，Tn会具有不同的形式。”
“……这些我都已经了解了……”小P嘟嘟囔囔。
“看看……”老C没有理会小P的嘟囔，“这就是一个典型的待定系数问题，如果我们将An、Bn、Cn看作系数，而将α、β、γ看作变量，通过给出不同的α、β、γ值和对应的Tn值，就可以求出相应的An、Bn、Cn。”
“哦？”小P停止了心不在焉，“那么怎么才可以根据α、β、γ的值找到对应的Tn值，然后反过来求出An、Bn、Cn呢？”
“可以先找到一个特定的Tn通项，再根据T0 = α 和Tn = Tn-1 + β + γn 来猜测此Tn对应的α、β、γ。好处是我们把根据α、β、γ和Tn = Tn-1 + β + γn 来猜测Tn的过程反了过来，因为从α、β、γ和Tn = Tn-1 + β + γn 来猜测Tn的过程是逆向思维，然而从Tn通项和T0 = α、Tn = Tn-1 + β + γn来猜测Tn对应的α、β、γ是正向思维——一般来说正向思维会比对应的逆向思维来得简单许多啊。接下来的工作就是根据我们猜测的结果对An、Bn、Cn求解。”
“那么应当怎么解呢？”小P问道。
“其实就是和一般的待定系数法的思想是一样的，给出一个我们已经知道的特解——这个解一般都是比较容易看出来或者推导出来的——将这个特解代入原方程，并
化简，可以得到一个关于系数的方程；再猜测一个特解，代入原方程，化简后又得到一个关于系数的方程……如果我们得到待定系数个数的方程——比如我们待定3
个系数——我们可以通过3个特解得到3个关于这3个系数的方程，若这3个方程联立后可解，那么我们就可以通过方程组解得这3个系数。”老C擦擦唾沫。
“就像通常使用待定系数法一样，我们可以试着从最简单的情况开始。”老C说，“我可以先假设Tn是一个常数数列，它的通项就是Tn = c，那么根据T0 = α，我们可以得到α = c；根据Tn = Tn-1 + β + γn，可以得到c = c + β + γn，根据这个式子，我们可以得到一个解——解可能有很多个，但是我们只要得到一组解就可以了——β = 0，γ ＝ 0；这样我们根据Tn的通项公式Tn =αAn + βBn + γCn就知道了在α = c，β = 0，γ ＝ 0的情况下，Tn是一个常数数列Tn = c，而在α = c，β = 0，γ ＝ 0的情况下Tn = αAn + βBn + γCn可以化简为Tn = cAn，而Tn实际上是Tn = c，所以c = cAn，所以An = 1。”
“哦？如果你把过程写在白板上，我可能会更清楚一些。”小P说道。
“好的。”老C一边答应小P，一边将推导的过程记录在白板上，“在这里我们先找到一个特解，由于这个特解是如此的特殊，当我们将这个解代入原方程——就是Tn =αAn + βBn + γCn后，不用再通过联立后面2个方程解方程组，系数An就很容易的被求出来了……买糕的佛祖，这个特解找的也太nb了。”
“……是啊是啊……”小P奇怪自己怎么就找不到这样一个奇妙的特解，“你还可以再找到2个特解吗？因为我们还有2个待定的系数需要求解。”他问道。
“嘻嘻，其实就是运气好，恰好猜出来而已。”老C谦虚的说，“不过猜也要有道理的猜，我们解决实际问题其实就是在有道理的猜嘛……”说着他又在白板上演算起来。“我们的第2个特解，是Tn = n，因为Tn = n可以表示成为n = (n-1) + 1，即Tn = Tn-1 + 1，所以我们的第2个特解很轻松的就出来了，根据Tn = Tn-1 + β + γn，我们可以猜测在Tn = n时，β = 1，γ = 0。而由Tn
= n和T0 = α，我们猜测α = 0也就很是合情合理了。所以我们又神奇的得到第2个特解：Tn = n，α = 0，β = 1，γ = 0。现在我们要做的就是将这个特解代入原方程Tn = αAn + βBn + γCn，来得到我们的第2个关于An、Bn、Cn的方程。”
“呵呵，这个步骤就由我来完成吧。”小P忍不住也想比划比划，“这样将Tn = n，α = 0，β = 1，γ = 0代入原方程，我们得到n
= Bn，不会吧，Bn也这么容易的就求出来了？”小P有些佩服老C的rp了。
“嗯，看来我们的rp保持了较高的水准。”老C赞叹道，“下一组我决定使用Tn = n2，因为n2 = (n - 1)2 – 1 + 2n，所以Tn可以表示为Tn = Tn-1
-1 +2n，根据Tn = Tn-1 + β + γn，我们又可以很轻易的猜测出β
= -1，γ ＝ 2，根据T0 = α可以得到α = T0 = 02 = 0，这样第3个特解就是Tn = n2，α = 0，β = -1，γ ＝ 2……”
“我来我来……”小P道，他一边说，一边在白板上演算，“将Tn = n2，α = 0，β = -1，γ ＝ 2代入原方程Tn
= αAn + βBn
+ γCn，得到n2
= -Bn + 2Cn，看来在这里我们还需要和先前的2个系数方程进行联立了，不过也很简单，因为已经求出Bn = n了，代入n2 = -Bn
+ 2Cn，得到n2 = -n + 2Cn，所以Cn = n(n + 1)/2。”
“现在我们可以总结一下啦，如果一个数列具有T0
= α，Tn = Tn-1
+ β + γn的递推公式，那么它的通项总可以写为T0 = α，Tn = α + βn + γn(n + 1)/2。”老C说道，并将这个结论写在了白板上。
“那么这个结论有什么用处呢？”小P问道。
“问得好。”老C回答，“这样我们起码可以确定形状和下面这个求和公式类似的问题的解啦。”说罢他在白板上写下一个公式。
“因为类似的求和公式可以表示为一个递推公式，且形式与我们刚才求解的递推公式类似，所以我们可以很轻松的运用我们刚才的结论求解此类求和问题。”说罢老C又在白板上继续比划起来。
“看看，除了我们观察问题的地方从希腊遨游回到一个和陕西差不多大的小岛，其余没有什么质的变化。”老C道，“我们先去吃饭，等回来我们再做一些练习来熟悉这个工具，为以后的应用做些准备。”
(这不是他们今天谈论的所有内容)