先來個游戲
我們先來做一個游戲。第一個人先從1和2中挑一個數(shù)字，第二個人可以在對方的基礎(chǔ)上選擇加1，或者加2。然后又輪到了第一個人，他可以再次選擇加1，或者加2，之后把選擇權(quán)交給對方。就這樣雙方交替地選擇加1或者加2，誰要是正好加到20，誰就贏了。用什么策略保證一定能贏？
為了方便你理解，我們舉一個實際的例子，當(dāng)然加到20的時間太長，我們假設(shè)加到10。假如我讓你先選，你選了2。接下來我選擇加2，這樣我加到了4，然后你選擇加1，你加到了5，這時我還會選擇加2，就加到了7。接下來，不論你選擇加1到8，還是加2到9，我都能加到10，因此我贏定了。當(dāng)然，你可能覺得先作選擇的人吃虧，那么這次我先來。我選擇1，你可能會選擇加2到3，然后我選擇加1到4。接下來，假如你選擇加2到6，我會選擇加1到7，這又回到第一次最后的狀態(tài)了，我還是贏了。
可能你已經(jīng)從上面的例子中想清楚這道題里面的技巧了，如果你還沒有想清楚，我再等你五秒鐘……好了，我們回來講講這道題。其實如果僅僅是搶10，情況并不復(fù)雜，你即使想不清楚它的道理，試幾次也能找到規(guī)律，但是如果是搶20，情況就復(fù)雜多了。如果是搶30，搶50呢？就不能通過窮舉法這種笨辦法解決問題了，就必須找它的規(guī)律了。
可能你已經(jīng)看出來了。要想搶到20，就需要搶到17，因為搶到了17，無論對方是加1還是加2，你都可以加到20。而要想搶到17，就要搶到14，以此類推，就必須搶到11、8、5和2。因此對于這道題，只要第一個人搶到了2，他就贏定了。這里面最核心的地方在于看清楚，無論對方選擇1還是2，你都可以讓這一輪兩個人加起來的數(shù)值等于3，于是你就可以牢牢控制整個過程了。
遞歸
那么這道看似是智力題的面試題是要考察候選人的什么技能呢？就是對計算機(jī)遞歸思想的理解。對于一般的人，讓他們數(shù)數(shù)，數(shù)到20。他們會從小往大數(shù)，但是這道題的解題思想正好相反。它是要尋找20，就要先尋找17，至于怎么從17到20，方法你是知道的。接下來要尋找17，就要尋找14，等等，這就是遞歸的思想。
倒推與減法
上述思想其實在我們做事情的時候也經(jīng)常采用。比如我要完成一本書的出版，有兩個辦法，一個辦法是順序估算每一個任務(wù)的時間。首先我要在一個月內(nèi)交稿，出版社要在一個月內(nèi)完成一校，然后我在某個時間完成修改，最后在某月某日出版，這是一種做法。
還有一種做法是倒推，或者倒逼。比如我們要在"雙十一"前上市銷售，那么書就必須在11月1日入庫，在10月15日開印，在10月5日定稿，等等，然后倒推我交稿的時間，一校、二校完成的時間等等。
哪種工作方式更有效呢？通常是后一種。另外，如果按照后一種方式工作，你會發(fā)現(xiàn)很多事情根本不可能在規(guī)定的時間做完，那么怎么辦呢？辦法很簡單，就是做減法。你可以認(rèn)為，上面這種工作方法，其實和計算機(jī)思維中的遞歸在原理上是一致的。
游戲升級
上面這道面試題，可能有點過于簡單，但是面試官其實還留有了兩個后手。
首先，他會問面試者，按照上述方法，從一開始（以1為起點）加到20，有多少種不同的遞加過程？比如1，4，7，10，12，15，18，20是一種；2，5，8，11，14，17，20又是一種。那么這樣的過程有多少種呢？這道題顯然不簡單了吧？下面我再給你5秒鐘想一下。
好了，5秒鐘時間過去了，我估計絕大部分人還是想不出來。事實上，面試Google的人大部分在兩分鐘內(nèi)根本想不出這道題的答案，更不要說5秒鐘了。因此你如果沒有想出來，不要氣餒，接下來我給你一講就明白了。
斐波那契數(shù)列
解這道題的技巧也在于使用遞歸，如果你從1，2，3開始找規(guī)律就難了。我們假定數(shù)到20有F（20）種不同的路徑，那么到達(dá)20這個數(shù)字，前一步只有兩個可能的情況，即從18直接蹦到20，或者從19數(shù)到20。
由于從18蹦到20，和19到20，彼此是不同的，因此走到20的路徑數(shù)量，其實就是走到18的路徑數(shù)量，加上走到19的路徑數(shù)量，也就是說F（20）＝F（18）＋F（19）。類似地，F(xiàn)（19）＝F（18）＋F（17）。這就是遞推公式。
最后，F(xiàn)（1）只有一個可能性，就是1，F(xiàn)（2）有兩個可能性，要么直接蹦到2，要么從1走到2。知道了F（1）和F（2），就可以知道F（3），然后再倒著推導(dǎo)回去，一直到F（20）即可。
數(shù)學(xué)比較好的朋友，可能已經(jīng)看出來這是著名的斐波那契數(shù)列，如果我們認(rèn)為F（0）也等于1，那么這個數(shù)列是這樣的，1（＝F（0）），1，2，3，5，8，13，21，……這個數(shù)列幾乎按照幾何級數(shù)的速度增長，到了F（20），就已經(jīng)是10946了。因此，靠窮舉法是不可能把所有情況想清楚的。
等價性原則
在數(shù)學(xué)和計算機(jī)上，還有一個非常重要的原則，就是等價性原則，也就是說很多問題是等價的。比如說，我再給你出一道題，如果一個樓梯有20層，你每次可以走一層或者兩層，爬到20層有多少種走法？這個問題的解，和搶20是一樣的，也是斐波那契數(shù)列。
總結(jié)
今天，我通過一個不算太復(fù)雜的問題，再一次講解了遞歸的思想，你把它理解為生活和工作中的倒逼就好了。另外，我再一次強(qiáng)調(diào)了計算機(jī)科學(xué)和數(shù)學(xué)中的等價性原則，掌握了這個原則，就可以把很多問題歸結(jié)為一類問題，解決了其中的一個，其他的就迎刃而解。
今天給大家留兩道思考題：
- 搶40的策略，每個人每次可以選擇加1到4中的任何一個數(shù)字，如果你先開始，你怎樣能贏？
- 能否談?wù)勀銓ぷ髦袑Φ贡频姆椒ǖ捏w會？
轉(zhuǎn)載至：吳軍的谷歌方法論20180619
