標(biāo)題: 神奇的遞歸 [打印本頁(yè)]
作者: 51hei麗人    時(shí)間: 2016-6-20 23:14
標(biāo)題: 神奇的遞歸
學(xué)習(xí)遞歸是很神奇的。。
【前言】首先我得告訴你，這篇文章中充滿了遞歸。如果你還不清楚遞歸，那么就準(zhǔn)備進(jìn)入邏輯的瘋狂吧。




【故事2則】
1.【從前有座山】（遞歸短文）
從前有座山.山里有座廟.廟里有個(gè)老和尚和小和尚. 老和尚對(duì)小和尚說:“從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:"從前有座山.山里有座廟. 廟里有個(gè)老和尚和小和尚.老和尚對(duì)小和尚說:……""""""""""""""”
………………（如果你把上文一字不漏的看完了，你會(huì)堆棧溢出的。。）……………………



2.【生活中的遞歸】
        假設(shè)你正在看新聞聯(lián)播正在播放胡總視察基層工作，突然插播一條來自美國(guó)的現(xiàn)場(chǎng)報(bào)道；這條插播還沒完，又插播一條來自敘利亞的現(xiàn)場(chǎng)報(bào)道……然后回到美國(guó)的報(bào)道；美國(guó)報(bào)道結(jié)束后，胡總又出現(xiàn)在屏幕上。這樣，在一個(gè)視頻內(nèi)中斷主視頻引用了另一個(gè)視頻實(shí)際上也是遞歸。


    從某種角度看，這個(gè)世界就是遞歸的，所以在你知道遞歸的那一天，你可以大聲地說：“我發(fā)現(xiàn)世界的本質(zhì)啦哈哈哈哈哈哈哈哈哈，這個(gè)世界的本質(zhì)就是‘我發(fā)現(xiàn)世界的本質(zhì)啦哈哈哈哈哈哈哈哈哈，這個(gè)世界的本質(zhì)就是……’”






理解遞歸是一件很值得自豪的事，遞歸在很多方面都有應(yīng)用，它不僅僅是一種優(yōu)秀的算法，更是一種先進(jìn)的思想，（類似于分治思想）即使你沒有學(xué)編程也沒有關(guān)系。如果你理解了它，至少證明你的智商不容懷疑。。


【關(guān)于頭痛的遞歸】


【Google英文搜索遞歸：（冷笑話一個(gè)，初識(shí)遞歸從笑話開始。。）】

（注："Did you mean:Recursion"的意思是：“你是不是在找：‘遞歸’”）




【“遞歸”告訴你：】如果你想理解遞歸，你就先要理解遞歸。(這句話只有你理解了遞歸之后你才能理解。。。)



    遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。是指函數(shù)/過程/子程序在運(yùn)行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。就好像是循環(huán)，但相對(duì)來說，比循環(huán)更難理解。



【遞歸經(jīng)典例子：】
【階乘】


在數(shù)學(xué)里，階乘函數(shù)是這樣定義的：


F(x)=1                （x=1時(shí)）
   或 x*F(x-1)       （x>1時(shí)）



解釋：
任意一個(gè)大于0的自然數(shù)的階乘結(jié)果為：
    當(dāng)這個(gè)自然數(shù)為1時(shí)，結(jié)果為1
    當(dāng)這個(gè)自然數(shù)大于1時(shí)，其結(jié)果為這個(gè)自然數(shù) 乘以 （這個(gè)自然數(shù)-1）的階乘



【菲波拉契數(shù)列】
菲波拉契數(shù)列，又稱黃金分割數(shù)列。

菲波拉契數(shù)列的規(guī)律是：列表中的任意一個(gè)數(shù)等于前面兩個(gè)數(shù)之和。通常列表的第一項(xiàng)是1.

也就是說，菲波拉契數(shù)列是這個(gè)樣子：
1、1、2、3、5、8、13、21、……

在數(shù)學(xué)中，菲波拉契數(shù)列被用遞歸定義：
Fib(n)=0 ,n=0
Fib(n)=1 ,n=1
Fib(n)=Fib(n-1)+Fib(n-2) ,n>1


也就是說，任意一個(gè)項(xiàng)可以這樣求得：（n為項(xiàng)數(shù)。(n為自然數(shù))）
如果需要求的項(xiàng)數(shù)為0，那么結(jié)果為  0
如果需要求的項(xiàng)數(shù)為1，那么結(jié)果為  1如果需要求的項(xiàng)數(shù)>1，那么結(jié)果為    菲波拉契數(shù)列中的第n-1項(xiàng) 與 菲波拉契數(shù)列中的第n-2項(xiàng) 之和。



【練習(xí)】：
用上面的方法手動(dòng)求菲波拉契數(shù)列的第3項(xiàng)，和3的階乘。




【如果你弄懂了……】
如果你弄懂了而且還沒學(xué)過編程，那么你是高智商無疑了。。自信的留言自豪一下吧。。
如果沒有弄懂了遞歸，那么你需要弄懂遞歸。（或者說找另一個(gè)人來幫你理解一下這篇文章。。）





【傳說中先進(jìn)的遞歸思想�。ńㄗh你一定要看看）】
【漢諾塔(hanoi)】


漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。



這個(gè)游戲的目標(biāo)是，借助Y塔，將X塔上的所有盤子移到Z塔上。但一次只準(zhǔn)移動(dòng)一個(gè)盤子，而且只準(zhǔn)把小盤子壓在大盤子上，而不允許將大盤子壓在小盤子上。
這看起來似乎很麻煩，難道不是嗎？但實(shí)際上3個(gè)盤子還是很好辦的，7步。（2個(gè)盤子最好辦），但是漢諾塔有他的難度等級(jí)，有些瘋子甚至喜歡玩11階、甚至是16階漢諾塔。
這聽起來好像很簡(jiǎn)單，真的嗎？以下是8階漢諾塔的解法：（255步）
8階漢諾塔解法0.
1.X ==> Y
2.X ==> Z
3.Y ==> Z
4.X ==> Y
5.Z ==> X
6.Z ==> Y
7.X ==> Y
8.X ==> Z
9.Y ==> Z
10.Y ==> X
11.Z ==> X
12.Y ==> Z
13.X ==> Y
14.X ==> Z
15.Y ==> Z
16.X ==> Y
17.Z ==> X
18.Z ==> Y
19.X ==> Y
20.Z ==> X
21.Y ==> Z
22.Y ==> X
23.Z ==> X
24.Z ==> Y
25.X ==> Y
26.X ==> Z
27.Y ==> Z
28.X ==> Y
29.Z ==> X
30.Z ==> Y
31.X ==> Y
32.X ==> Z
33.Y ==> Z
34.Y ==> X
35.Z ==> X
36.Y ==> Z
37.X ==> Y
38.X ==> Z
39.Y ==> Z
40.Y ==> X
41.Z ==> X
42.Z ==> Y
43.X ==> Y
44.Z ==> X
45.Y ==> Z
46.Y ==> X
47.Z ==> X
48.Y ==> Z
49.X ==> Y
50.X ==> Z
51.Y ==> Z
52.X ==> Y
53.Z ==> X
54.Z ==> Y
55.X ==> Y
56.X ==> Z
57.Y ==> Z
58.Y ==> X
59.Z ==> X
60.Y ==> Z
61.X ==> Y
62.X ==> Z
63.Y ==> Z
64.X ==> Y
65.Z ==> X
66.Z ==> Y
67.X ==> Y
68.Z ==> X
69.Y ==> Z
70.Y ==> X
71.Z ==> X
72.Z ==> Y
73.X ==> Y
74.X ==> Z
75.Y ==> Z
76.X ==> Y
77.Z ==> X
78.Z ==> Y
79.X ==> Y
80.Z ==> X
81.Y ==> Z
82.Y ==> X
83.Z ==> X
84.Y ==> Z
85.X ==> Y
86.X ==> Z
87.Y ==> Z
88.Y ==> X
89.Z ==> X
90.Z ==> Y
91.X ==> Y
92.Z ==> X
93.Y ==> Z
94.Y ==> X
95.Z ==> X
96.Z ==> Y
97.X ==> Y
98.X ==> Z
99.Y ==> Z
100.X ==> Y
101.Z ==> X
102.Z ==> Y
103.X ==> Y
104.X ==> Z
105.Y ==> Z
106.Y ==> X
107.Z ==> X
108.Y ==> Z
109.X ==> Y
110.X ==> Z
111.Y ==> Z
112.X ==> Y
113.Z ==> X
114.Z ==> Y
115.X ==> Y
116.Z ==> X
117.Y ==> Z
118.Y ==> X
119.Z ==> X
120.Z ==> Y
121.X ==> Y
122.X ==> Z
123.Y ==> Z
124.X ==> Y
125.Z ==> X
126.Z ==> Y
127.X ==> Y
128.X ==> Z
129.Y ==> Z
130.Y ==> X
131.Z ==> X
132.Y ==> Z
133.X ==> Y
134.X ==> Z
135.Y ==> Z
136.Y ==> X
137.Z ==> X
138.Z ==> Y
139.X ==> Y
140.Z ==> X
141.Y ==> Z
142.Y ==> X
143.Z ==> X
144.Y ==> Z
145.X ==> Y
146.X ==> Z
147.Y ==> Z
148.X ==> Y
149.Z ==> X
150.Z ==> Y
151.X ==> Y
152.X ==> Z
153.Y ==> Z
154.Y ==> X
155.Z ==> X
156.Y ==> Z
157.X ==> Y
158.X ==> Z
159.Y ==> Z
160.Y ==> X
161.Z ==> X
162.Z ==> Y
163.X ==> Y
164.Z ==> X
165.Y ==> Z
166.Y ==> X
167.Z ==> X
168.Z ==> Y
169.X ==> Y
170.X ==> Z
171.Y ==> Z
172.X ==> Y
173.Z ==> X
174.Z ==> Y
175.X ==> Y
176.Z ==> X
177.Y ==> Z
178.Y ==> X
179.Z ==> X
180.Y ==> Z
181.X ==> Y
182.X ==> Z
183.Y ==> Z
184.Y ==> X
185.Z ==> X
186.Z ==> Y
187.X ==> Y
188.Z ==> X
189.Y ==> Z
190.Y ==> X
191.Z ==> X
192.Y ==> Z
193.X ==> Y
194.X ==> Z
195.Y ==> Z
196.X ==> Y
197.Z ==> X
198.Z ==> Y
199.X ==> Y
200.X ==> Z
201.Y ==> Z
202.Y ==> X
203.Z ==> X
204.Y ==> Z
205.X ==> Y
206.X ==> Z
207.Y ==> Z
208.X ==> Y
209.Z ==> X
210.Z ==> Y
211.X ==> Y
212.Z ==> X
213.Y ==> Z
214.Y ==> X
215.Z ==> X
216.Z ==> Y
217.X ==> Y
218.X ==> Z
219.Y ==> Z
220.X ==> Y
221.Z ==> X
222.Z ==> Y
223.X ==> Y
224.X ==> Z
225.Y ==> Z
226.Y ==> X
227.Z ==> X
228.Y ==> Z
229.X ==> Y
230.X ==> Z
231.Y ==> Z
232.Y ==> X
233.Z ==> X
234.Z ==> Y
235.X ==> Y
236.Z ==> X
237.Y ==> Z
238.Y ==> X
239.Z ==> X
240.Y ==> Z
241.X ==> Y
242.X ==> Z
243.Y ==> Z
244.X ==> Y
245.Z ==> X
246.Z ==> Y
247.X ==> Y
248.X ==> Z
249.Y ==> Z
250.Y ==> X
251.Z ==> X
252.Y ==> Z
253.X ==> Y
254.X ==> Z
255.Y ==> Z

我相信沒有哪個(gè)瘋子會(huì)把上面的東東一字一句的看完
這很瘋狂，不是嗎？那回到正題，3階漢諾塔又怎么個(gè)解法呢？
這就需要用我們神奇的遞歸思想了：

從前，有一個(gè)人叫A，他看到3階漢諾塔毫無頭緒。他有一堆幫手。
有一天這個(gè)A先生突發(fā)奇想，他想：我現(xiàn)在不知道3階漢諾塔怎么移動(dòng)到Z，但是要是有一個(gè)人幫我把X塔上的上面2個(gè)盤子移動(dòng)到Y(jié)塔，我豈不是只需要移動(dòng)最后一個(gè)盤子，然后再讓他用同樣的方法把Y塔上的2個(gè)盤子移動(dòng)到Z上，問題不就解決了？？？
于是他命令B把2個(gè)盤子移動(dòng)到Y(jié)上去……結(jié)果哪知道這B居然不知道怎么移。但他想：我現(xiàn)在不知道2階漢諾塔怎么移動(dòng)到Y(jié)，但是要是有一個(gè)人幫我把X塔上的上面1個(gè)盤子移動(dòng)到Z塔，我豈不是只需要移動(dòng)最后一個(gè)盤子，然后再讓他用同樣的方法把Z塔上的1個(gè)盤子移動(dòng)到Y(jié)上？
……………………
……………………
于是問題就解決了！就像這樣↓
3階漢諾塔解法0.
1.X ==> Z
2.X ==> Y
3.Z ==> Y
4.X ==> Z
5.Y ==> X
6.Y ==> Z
7.X ==> Z





【我想，現(xiàn)在這些遞歸經(jīng)典例子你應(yīng)該能理解了……：】
【階乘】


在數(shù)學(xué)里，階乘函數(shù)是這樣定義的：


F(x)=1                （x=1時(shí)）
   或 x*F(x-1)       （x>1時(shí)）



解釋：
任意一個(gè)大于0的自然數(shù)的階乘結(jié)果為：
    當(dāng)這個(gè)自然數(shù)為1時(shí)，結(jié)果為1
    當(dāng)這個(gè)自然數(shù)大于1時(shí)，其結(jié)果為這個(gè)自然數(shù) 乘以 （這個(gè)自然數(shù)-1）的階乘



【菲波拉契數(shù)列】
菲波拉契數(shù)列，又稱黃金分割數(shù)列。

菲波拉契數(shù)列的規(guī)律是：列表中的任意一個(gè)數(shù)等于前面兩個(gè)數(shù)之和。通常列表的第一項(xiàng)是1.

也就是說，菲波拉契數(shù)列是這個(gè)樣子：
1、1、2、3、5、8、13、21、……

在數(shù)學(xué)中，菲波拉契數(shù)列被用遞歸定義：
Fib(n)=0 ,n=0
Fib(n)=1 ,n=1
Fib(n)=Fib(n-1)+Fib(n-2) ,n>1


也就是說，任意一個(gè)項(xiàng)可以這樣求得：（n為項(xiàng)數(shù)。(n為自然數(shù))）
如果需要求的項(xiàng)數(shù)為0，那么結(jié)果為  0
如果需要求的項(xiàng)數(shù)為1，那么結(jié)果為  1如果需要求的項(xiàng)數(shù)>1，那么結(jié)果為    菲波拉契數(shù)列中的第n-1項(xiàng) 與 菲波拉契數(shù)列中的第n-2項(xiàng) 之和。











【程序中的遞歸】
    前面提到遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。
    是指函數(shù)/過程/子程序在運(yùn)行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。
    那么，遞歸在程序中如何實(shí)現(xiàn)呢？

        我們就以經(jīng)典的“漢諾塔”為例，編寫得這樣一個(gè)程序：



#include <iostream.h>
#include <stdlib.h>
int n;
void mov(char a,char b);
//漢諾塔函數(shù)作用：遞歸主體部分。。
//參數(shù)解釋：[n]:漢諾塔階數(shù)。 [Start]:起始塔的名稱。（如：X） [Temp]:臨時(shí)塔的名稱 [End]:目標(biāo)塔的名稱。
void hanoi(unsigned int n,char Start,char Temp,char End) {
    if (n==1) {    //如果只有一階,
        mov(Start,End);    //那么直接將起始塔上的盤子移動(dòng)到目標(biāo)塔
    } else if (n>=2) {    //如果不止一階        hanoi(n-1,Start,End,Temp);//(注意此處參數(shù)變化!)那么將除了最低端的盤子上面的所有盤子移動(dòng)到臨時(shí)塔
        mov(Start,End);            //移動(dòng)最大的一個(gè)盤子(偷懶的過程在此)
        hanoi(n-1,Temp,Start,End);    //(注意此處參數(shù)變化!)用同樣的方法將臨時(shí)塔上的盤子移到目標(biāo)塔上
    }
}
void mov (char a,char b) { //mov函數(shù)作用：在屏幕上輸出這一個(gè)步驟。（模擬移動(dòng)的過程）
    cout<<a;
    cout<<">";
    cout<<b;
    cout<<endl;
    system("pause");
}
void main (void) {
    cout<<"請(qǐng)輸入漢諾塔階數(shù)：";
    cin>>n;
    cout<<"步驟如下:";
    cout<<endl;
    hanoi(n,'A','B','C');
    cout<<"完成！";
    cout<<endl;
    system("pause");
}

程序很短，應(yīng)該算是很易于理解吧。



【關(guān)于遞歸思想的冷笑話】
（如果你知道什么是遞歸了……那么看一個(gè)遞歸笑話吧……）


當(dāng)你理解了遞歸后，你可以使用先進(jìn)的遞歸思想解決實(shí)際問題：
我不知道什么是遞歸，我想要理解遞歸。要是有人幫我理解什么是“遞歸”那我豈不是不用理解了嗎？于是找到另外一個(gè)人，要他理解一下遞歸。結(jié)果他也不知道什么是遞歸，他想要理解遞歸。要是有人幫他理解什么是“遞歸”那他豈不是不用理解了嗎？于是他又找到另一個(gè)人，結(jié)果另一個(gè)人也不知道什么是遞歸，但那個(gè)人想，要是有人幫他理解什么是“遞歸”那他豈不是不用理解了嗎？于是……最終結(jié)果是【棧溢出】！





您看懂了遞歸（指遞歸（指遞歸（指遞歸（指遞歸（指遞歸（指遞歸）））））））了嗎？請(qǐng)?zhí)岢瞿慕ㄗh！謝謝！







歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1