“雖然自然辯證法這個理論是絕對正確的，但是我總感覺對解決實際問題的幫助不是很大。”小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道，“我們先去吃飯，等回來我們再做一些練習來熟悉這個工具，為以后的應用做些準備。”
(這不是他們今天談論的所有內容)