看什麼書適合學習遞歸論？
以前上數據結構時上到遞歸的內容,老師不讓我們看嚴蔚敏的那本教材,他說要看另外的書,有專門的書講這個,但是具體哪本也因為沒到時候,所以沒說.
後來忘了問他了,現在沒機會問了,只好到知乎上問問,該看哪本書?==============================天啊 你們和我想的多不一樣:
學了半年遞歸論，認真一答：
如果智商高：直接上Soare
O.W.：一開始Cutlan配著Cooper看，看到中間扔Cutland，Cooper配著Smullyan看，到一定時間扔Cooper，Smullyan配著Soare看。最後直接啃Soare。（從此題主走上了徹底點歪技能樹之路……逃）Cutland, N. (1980). Computability: An introduction to recursive function theory. Cambridge university press.Cooper, S. B. (2003). Computability theory. CRC Press.Smullyan, R. M. (1993). Recursion theory for metamathematics.Soare, R. I. (1987). Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. Springer Science Business Media.
題主你就不要怪大家了，「遞歸論」這個叫法確實很小眾。我也是看了wiki才知道這個叫法的。如果你現在是剛剛學完數據結構的水平，建議先不要考慮學「遞歸論」了，這真的是一個理論計算機領域一個難而小的分支。
先系統的按順序的學一下「可計算性理論」和「數理邏輯」。當然，如果你能「系統」地學下來，相比同齡人就已經很厲害了，那個時候如果還對理論計算機感興趣，再去研究「遞歸論」吧。
我系統的學過前面這兩門課，並且不系統的看過你所謂的「遞歸論」的東西。不過不是用中文或者英文，所以就不給你推薦了。
最後，你如果不去學前面兩門課，當然也能勉強看懂，但是理解不會太深刻。--------看到好多提到scheme的回答，可能是因為大家覺得因為函數式語言中遞歸作用更大（把primitive recursive也用recursive來實現）？Church-Turing Thesis說了，lambda、圖靈機、遞歸是三種同等計算能力的模型（或者說目前能夠機械實現的模型）。了解其中一種遞歸的具體應用只不過能增加一些關於「遞歸」的見識罷了。「遞歸論」涉及的東西是從更抽象的角度來描述的。題主給的目錄中感覺只是比較淺的一些，大部分抽象的東西是用高階邏輯表述的。《遞歸可枚舉集和圖靈度:可計算函數與可計算生成集研究》
.
我說一下吧。
遞歸論的入門讀物比較多，個人推薦Cutland的"computability"。這本書不論是對數學還是計算機系的學生都比較合適。尤其是對於Godel定理的純粹的遞歸論處理方式對後續的學習會有比較大的幫助。
學完Cutland之後如果不想深究遞歸論，看看Cooper的"computability theory"也不錯。Cooper的書並不比Cutland的深很多，但是覆蓋了遞歸論裡面更廣的內容。
如果想比較深入地看遞歸論，Soare的 "Recursively enumerable sets and degrees"前面幾章比較合適。Soare的書一般看到有窮損害再加上樹方法構造minimal pair差不多就可以了。現在遞歸論的學生基本不學0"""方法。
另外還推薦Sacks 於60年代寫的一本小冊子："degrees of unsolvability"。這本書雖然年代很久，但是非常值得一讀。
純粹度論值得看的還有Richard Shore的"The Turing Degrees: An Introduction"。他主頁上就有。其餘Lerman, Odifreddi等人的著作只能作為參考書翻翻。
如果想學higher recursion或者對於描述集合論有興趣，那麼可以看看Sacks的"higher recursion theory"。這是一本極好的著作。
如果對於反推數學有興趣，那麼必須看的就是"Subsystems of Second Order Arithmetic"。
如果對於演算法資訊理論有興趣，可以看看Andre Nies的"computability and randomness"或者Downey-Hirschfeldt的"algorithmic randomness theory"。
總之看你對哪個方向有興趣. 或者你都有興趣，就都看看。但是不主張把所有書都從頭到尾看一遍。只要掌握一些基本的內容就行了，以後如果做研究要用到可以再回來翻翻。
但即使你沒有興趣研究遞歸論而只感興趣集合論，證明論或者模型論，這個方向的知識也是必須掌握的。理解了遞歸論對於學習集合論是非常關鍵的。內模型理論，描述集合論都可以看成是遞歸論的推廣。證明論就更不用說了，它到處都在用遞歸論。古典的模型論與遞歸論聯繫也是非常緊密的。而且現在的遞歸模型論前途也未必不光明。卧槽，這目錄把我嚇到了。。學個遞歸，至於嗎！
數據結構課上跟遞歸相關的東西。。解遞歸方程算時間空間複雜度什麼的？去看《具體數學》唄。。
如果是編程怎麼用遞歸的話。。那應該是任何一本C語言教材的任務。。進階的話可以學點scheme了解尾遞歸。。然後這應該是數據結構課前就搞定的基礎吧在我看來，遞歸等於數學歸納法。
除了一般的數學歸納法，還有structural induction。
我覺得ullman的編程入門書foundations of computer science不錯，裡面有介紹。見下面的答案：如何學習遞歸?
這麼說吧，我一直覺得我已經深入理解遞歸的本質了，直到研究生時修了《計算理論》，我才知道以前的理解的遞歸連門都沒入
我在遞歸論里看到的遞歸和我在演算法與數據結構里看到的遞歸不一樣.
如果只需要了解，可以看S.E.P.的鏈接Recursive Functions (Stanford Encyclopedia of Philosophy)讀完後，覺得沒看懂也不想看，就算了。讀完後，覺得沒看懂但是更想看，就去Bibliography裡面找「年代較新」「看起來像書而不是論文「條目，符合條件的比如：Enderton, H.B., 2010, Computability Theory: An Introduction to Recursion Theory, Waltham, MA: Academic Press.
The Little Schemer
誰看誰知道。
麻煩大家不要亂抖機靈了。C程序設計的抽象思維 看看這本書
《C程序設計的抽象思維》
SICP
就是好多好多的小象啊
http://pan.baidu.com/s/1eQ4CA8i用了一點點c++ 。李戈講的https://www.coursera.org/instructor/ligechina
看一遍盜夢空間，會對遞歸有更深理解。
百度 漢諾塔問題找一個點擊率最高的博客看看 在打一打
多搜幾個博客看看得了，這東西書上即便寫，也就1、2頁而已。。
要想了解遞歸，首先要了解遞歸
--
抱歉我沒看題。。摺疊我吧。推薦閱讀：
※概率為 0 的事件，必然不能發生嗎？概率為 1 的事件，必然能發生嗎？
※如何用確鑿證據說明英文教材比中文教材好？
※為什麼無理數會存在於數學體系之中？（我當然不是問為什麼有數會除不盡的問題...）
※從一副殘缺的牌里隨機抽出一張牌，如何最科學地推測概率？
TAG:數學 | 數理邏輯SymbolicLogic | 遞歸論 |