現實中有什麼遞歸的場景嗎？

01-12

鑒於很多答主不明白什麼叫遞歸，背個書：
1.基準情形。你必須有某種基準情形，不用遞歸就能求解。如x=0時，y=1，這是固定的，不需要求f(x-1)。
2.不斷推進。對於那些遞歸求解的情形，遞歸調用必須總能夠朝著產生基準情形的方向推進。如，接上條，你的x的變化必須是向x=0推進，而不是向x=正無窮推進，後者不叫遞歸。
這兩條是遞歸的基準法則，概念都搞不清就強答的朋友們，你們意識到自己在誤導別人了嗎？

上過學的應該都知道怎麼從前往後傳卷子嗯。

卷子從講台或前面的同學傳到小明手中的時候，小明從卷子中拿走一張寫上自己的名字。如果小明發現前面同學拿到卷子之後沒有卷子可傳給自己，就報告老師（拋出異常）。

如果小明身後沒有人了，那就把多餘的卷子（可以是0）通過前面的同學層層遞還給老師；（即base case，基準情形）

如果小明身後還有人，那麼就把多餘的卷子交給下一個同學，由下一位同學繼續傳遞分發。（層層推進）

（巧得很，return同時具有「歸還」和「返回結果」的含義。）

寫成Java大概是醬的：

int handOut(Student xiaoming, int numOfPaper) { numOfPaper = xiaoming.takeOnePaper(numOfPaper); if (!xiaoming.hasNext()) { return numOfPaper; } else { return handOut(xiaoming.next(), numOfPaper); } }

Student大概就是醬吧：

public class Student { ... private boolean hasPaper; private Student next; ...

public int takeOnePaper(int numOfPaper) { if (numOfPaper &<= 0) { throw new IllegalArgumentException("老師！這裡沒試卷了！"); } this.hasPaper = true; return --numOfPaper; } public boolean hasNext() { return this.next != null; } public Student next() { return this.next; } }

至於為什麼要有爆棧，大概是因為人太多的話，等卷子傳到最後一個人的時候考試已經結束了2333333333

老師也可以選擇自己從前到後一個人一個人髮捲子（for循環），效果是差不多噠。

int handOut(List& group, int numOfPaper) { for (Student xiaoming : group) { numOfPaper = xiaoming.takeOnePaper(numOfPaper); } return numOfPaper; }

來感受一下大自然的智慧，DNA分子中的分治演算法~

一段DNA分子中有表達的部分，被稱為「外顯子」（Exon），還有不表達的部分，被稱為「內含子」（Intron）。DNA要表達蛋白質的時候需要把內含子先切掉再把外顯子接起來，但有時候一段內含子太長了，酶找到這段內含子的開頭和結尾需要很長時間（想像一下要截取一條超長鏈表的特定一部分），這怎麼辦呢？機智的DNA在內含子中加入了許多「遞歸分片位點」（Recursive Slicing Site），酶找到這些位點然後把大段DNA分成小段，再分成小小段，最後分到單個酶能解決的長度，然後再重新拼接起來。

相關論文：Sibley C R, Emmett W, Blazquez L, et al. Recursive splicing in long vertebrate genes[J]. Nature, 2015, 521(7552): 371-375.

另外還有些腦洞論文，用生物方法進行遞歸計算——

這個http://biorxiv.org/content/early/2015/05/01/018804 是用DNA進行Lambda演算……

這個Computing with Membranes 是用基本的膜操作來模擬遞歸函數……

你想抓子？

典型遞歸的話要調用自身，就是在情況A下做事做到一半，開始在情況B下做相同的事。

另一個是要有終止條件，不能無限遞歸下去。

比較恰當的有:

查字典或者看維基，想知道一個詞的意思，就去看它的解釋，解釋中在遇到不會的，再去看解釋－－終於有一個詞條里每個詞都能看懂了，這時候就返回，繼續看上一個詞的解釋。

傳紙條（假設對方還要傳回來一張，），一個人傳給自己左邊，然後那個人再傳給自己左邊，直到紙條傳到了，在寫張紙條返回，從右到左一個一個穿回來。

穿衣服與脫衣服。完美的具備遞歸形式、棧以及邊界條件。

當然脫別人的衣服可能稍有不同。

_____________________________________________________

單向尾遞歸版（有人覺得這玩意完全可以循環代替，那當然，只不過單純的循環沒法好好體現穿衣服的彈棧罷了，你得寫倆循環才可以）

def 脫衣服(衣服): if 衣服 == 0: #邊界條件做該做的事() #邊界處理 return 脫衣服(衣服 - 1) #遞歸情況

正常遞歸版

衣服 = xxxx def 脫衣服(): if 衣服 == 0: #邊界條件做該做的事() #邊界處理 return 衣服 = 衣服 - 1 #遞歸壓棧前狀態改變脫衣服() #遞歸情況衣服 = 衣服 + 1 #遞歸彈棧後狀態改變

雙人交換輪流脫衣服版

A的衣服 = xxxx B的衣服 = xxxx


def A脫衣服():

    if A的衣服 == 0 and B的衣服 == 0:

        做該做的事()

        return

    elif B的衣服 == 0:

        A的衣服 = A的衣服 - 1

        A脫衣服()

        A的衣服 = A的衣服 + 1

    else:

        B的衣服 = B的衣服 - 1

        B脫衣服()

        B的衣服 = B的衣服 + 1

def B脫衣服(): if A的衣服 == 0 and B的衣服 == 0: 做該做的事() return elif A的衣服 == 0: B的衣服 = B的衣服 - 1 B脫衣服() B的衣服 = B的衣服 + 1 else: A的衣服 = A的衣服 - 1 A脫衣服() A的衣服 = A的衣服 + 1

至於OO版什麼的……自己看著辦吧……

在電視上用了手機投屏功能，然後打開相機對準屏幕，就會出現遞歸了。

GNU』s not UNIX =&> (GNU』s Not UNIX)』s Not UNIX =&> ((GNU』s Not UNIX)』s Not UNIX)』s Not UNIX =&> …

請參考下面這個鏈接

http://www.zhihu.com/question/51903950

說一個不符合程序有窮性的遞歸。

那天競賽老師在隔壁給高一新生講解遞歸：

這個遞歸啊，在現實中有很多應用……比如說啊……這個……遞歸……

另一老段子：你要了解遞歸，你要先了解遞歸。

如果沒記錯劉汝佳在紫書上也是類似這麼寫的解釋的遞歸。

講個故事。

四個小夥伴參加考試，遇到一個誰都不能獨立解決的難題，但每個人還能回答上一部分來。

所以他們決定共同合作，用前後傳紙條的方式交流。

四個人坐成一列，分別是同學A,B,C,D，而他們遇到的難題是:

-----------------------------

四大名著有哪些？ O_o...

------------------------------

PLAN A

A只知道有《三國演義》，只能求助，紙條傳給B: 四大名著有什麼？

--&>B把紙條傳給C: 四大名著有什麼？

--&>C把紙條傳給D: 四大名著有什麼？

--&>D看完回復給C:記不全啊，我現在只知道有《西遊記》。

--&>C看完回復給B:記不全啊，我現在只知道有《西遊記》《紅樓夢》

--&>B看完回復給A:記不全啊，我現在只知道有《西遊記》《紅樓夢》《水滸傳》

--&>A看完紙條，他知道有《三國演義》，最後卷子在上寫好了完整答案，滿分！

這個過程就叫: 頭遞歸！

好像很完美的團隊合作，可是你發現有些詭異嗎？只有A知道了完整的答案，說好的同舟共濟呢。。。

------------------

那麼看一下PLAN B

A只知道有《三國演義》，只能求助了，紙條傳給B:

四大名著除了《三國演義》還有什麼？

--&>B想了想紙條傳給C:

四大名著除了《三國演義》《水滸傳》還有什麼？

--&>C想了想紙條傳給D:

四大名著除了《三國演義》《水滸傳》《紅樓夢》還有什麼？

--&>D想了想寫完了考題，回復給C:

我知道答案了，四大名著是《三國演義》《水滸傳》《紅樓夢》《西遊記》

--&> C回復B:

我知道答案了，四大名著是《三國演義》《水滸傳》《紅樓夢》《西遊記》

--&>B回復A:

我知道答案了，四大名著是《三國演義》《水滸傳》《紅樓夢》《西遊記》

--A收到信息，也知道了答案。

這個過程叫: 尾遞歸！

相比前一種，這次小夥伴們共同努力，全都回答對了問題，滿分！

----------------------

如果你能夠理解，頭遞歸和尾遞歸是怎麼一回事了。那你就能發現，大遞歸思想的核心: 把一個複雜的較大的問題，交給多個小過程而且每個小過程都完成一部分任務。同時還要有一個遞歸返回的條件(你都知道四本書名了，還會往後傳紙條嗎？)。

一次學院辯論賽，坐在最後一排的我看上第一排的妹紙，於是我對著前一排的人說，麻煩幫我問問第一排妹紙的名字。於是我前一排的人又將這句話傳到他的前一排，重複該過程直到第二排的人問第一排妹紙的名字時，所有人都在等待前一排的人返回妹紙的名字，當妹紙說出她名字時，觸發遞歸的返回條件，第二排的人將妹紙的名字返回給他的後一排，直到最後一排，於是我知道妹紙的名字了。

當然這事是我胡編的。

神給出生在世上的每一對男女賦予數字型大小碼牌。當男孩長大的時候，必須到神的面前，神告訴他去找持有相同號碼的女孩，而且男孩找到命定之人必須回來告訴神。於是男孩出發了，當他遇到兩條分叉路時，守路人就會讓他掏出數字型大小碼牌，如果這個數字型大小碼比守路人的數字型大小碼大，那男孩就往右邊走，如果這個數字型大小碼比守路人的數字型大小碼小，那男孩就往左走。當男孩遇到下兩條分叉路時，重複該過程......直到一天男孩的號碼和守路人的號碼相同時，守路人顯出女孩的真身。然後這對男女沿著原來相同的路返回到神的面前。如果男孩終生找不到女孩，那麼當男孩死亡(內存用盡)的時候就是程序崩潰的時候。

這是二叉查找樹(BST)的遞歸。

有的，鏡中鏡，電視直播畫面等

鏡子的遞歸最高票答案 @高天就是。

電視直播的遞歸，看圖，

演播室內有好多台電視機，每台電視機遞歸顯示一次直播畫面

global expectancy

def Life(): Awake（） Eat（） try： Work（） except TuoYanZheng： Play（） Others（option） Shit（） Sleep（） expectancy-= 1 if expectancy &<= 0： return "death" else： return Life（）

你爺爺調用了造人函數。。。

你爸爸調用了造人函數。。。

你本人調用了造人函數。。。

error ：找不到對象。。。

孟婆煮完湯，打算嘗嘗鹹淡。

喝了一口

。。。

湯被喝完了！

現實中，程序員寫遞歸，這本身就是現實場景。恰好昨晚10.24程序員節寫了個：

((lambda (lst ref) (let ([idx 0]) (((lambda (slash) ((lambda (f) (f f)) (lambda (f) (slash (lambda (x y z) ((f f) x y z)))))) (lambda (cross-slash) (lambda (lst ref idx) (cond [(empty? lst) #f] [(eq? ref (car lst)) idx] [else (cross-slash (cdr lst) ref (+ idx 1))])))) lst ref idx))) "(1 2 3 4 5 6 5 6) 5)

; ==&> 4