分享好文，中學生要學電腦嗎？
作者：創新工場CTO、人工智慧工程院執行院長 王詠剛
文章来自半轻人微信公众号（ban-qing-ren）
………………………………
朋友的孩子高中剛畢業，已拿到美國頂尖大學（非電腦專業）的錄取通知。疫情影響，不知何時才能去學校報到。孩子想抓緊學習一下程式設計，為大學打好基礎。這孩子找我聊了一個多小時，從如何學程式設計，聊到非電腦專業和電腦專業的路徑差異，又聊到如何從不同角度認識電腦與程式設計。聊得比較寬泛，不知是否對這孩子有用。
回想我自己的高中時代：那時雖迷戀程式設計，卻完全沒有懂行的人指導。在我們那個四線城市的廠礦中學裡，開設電腦興趣課的老師知道的資訊還沒我多。我高一時跑到北京中關村逛街，卻完全沒意識到中國第一代頂尖程式師當時就在我身邊的低矮辦公樓裡寫代碼（這話說得並不準確，比如求伯君那年就主要是在珠海做開發），鼎鼎大名的UCDOS、WPS、CCED就出自他們之手……我在當時街邊的一家書店（位置似乎就在今天的鼎好大廈對面）買到了許多種印刷品質極低劣的電腦圖書。用今天的標準看，那就是一批盜版影印或未授權翻譯的國外圖書。可那批書竟成了我高中時代最寶貴的程式設計知識來源。
顯然，我在高中時根本就是野路子學電腦。現在後悔也沒用，當時我的眼界或能觸及的資源就那麼多。如果能穿越回30年前，我該對喜歡程式設計的自己說些什麼呢？這些年，我與世界上最好的一批程式師合作過，也參與過世界上最有價值的軟體系統研發——我所積累的一些粗淺經驗裡，有哪些可以分享給一個愛程式設計的中學生？
【問題1】中學生要不要學電腦？
當然要！
每個中學生都要學。只不過——建議大部分中學生使用“休閒模式”，小部分（不超過10%）中學生使用“探險模式”。
啊？兩個模式？那我該進入哪個模式？⟹請跳轉至【問題2】
【問題2】選哪個模式？
你癡迷電腦嗎？比如，你玩遊戲時會特別想知道這遊戲背後的代碼是如何編寫的嗎？再比如，就算老師家長不同意你學電腦，甚至當著你的面把電腦砸了，你也要堅持學電腦嗎？如果是，恭喜你進入“探險模式”⟹請跳轉至【問題200】
你對數學有興趣嗎？比如，你看到街邊建築的曲線，就會在腦子裡琢磨曲線對應的函數或方程嗎？每當手裡攥著幾粒骰子，你就會不由自主地計算概率嗎？如果是，歡迎進入“探險模式”⟹請跳轉至【問題200】；當然，如果有些猶豫，也可以先進入“休閒模式”⟹請跳轉至【問題100】
即便你對電腦和數學興趣不大，家長、老師還是強烈建議你學電腦嗎？就算你一百個沒時間一千個不願意，家長、老師還是會逼著你學電腦嗎？如果是，建議你主動進入“休閒模式”並向家長、老師彙報說“我已經按照前谷歌資深軟體工程師的專業建議在認真學程式設計了”⟹請跳轉至【問題100】
其他情況，一律進入“休閒模式”。⟹請跳轉至【問題100】
【問題100】休閒模式 | 主要學什麼？
“休閒模式”將電腦視為我們生活、工作中的必備工具，主要學習如何聰明、高效、優雅地使用計算設備。這裡說的計算設備，包括所有形式的電腦、手機、遊戲機、智慧家電以及未來一定會進入生活的自動駕駛汽車。
什麼什麼？你已經會用電腦、會玩手機、會打遊戲了？別著急，慢慢往下看。
【問題101】休閒模式 | 我會用搜尋引擎嗎？
我知道你會用百度搜習題答案。但，習題答案不是知識。你會用搜尋引擎來搜索和梳理知識嗎？請試著用電腦和你喜歡的搜尋引擎來解決如下兩個問題：
（1）圓周率𝜋的計算方法有多少種？每種不同的計算方法分別是由什麼人在什麼時代提出的？借助電腦，今天人們可以將圓周率𝜋計算到小數點後多少位？將圓周率𝜋計算到小數點這麼多位元，一次大概需要花掉多少度電？
（2）全球大約有多少個廁所？在發展程度不同的國家，分別有多少比例的人可以享用安裝了抽水馬桶的衛生廁所？為什麼比爾·蓋茨曾大力推動一個設計新型馬桶的研發專案？比爾·蓋茨的公益組織在這個專案上大約花費了多少資金，最終收到了多大的效果？
如果你沒法快速得到上述問題的全部答案，那就給自己設一個小目標：一個月內，學會用搜尋引擎系統地獲取、梳理一組知識點的全部技巧。
【問題102】休閒模式 | 接下來學什麼？
建議學好典型的工具軟體。比如，我知道你會用Office了，但用Office和用Office是很不一樣的。對生活、學習、工作來說，學好、學透一個工具軟體比鑽研程式設計技巧更實用。
你會用Excel來管理班級公益基金的預算和實際收支情況嗎？
你會用Excel做出過去20年裡全球大學排名的演變趨勢圖嗎？
你會用Word排版一篇中學生論文嗎？論文中的圖表和最後的參考文獻部分該如何排版？
你會用Word編排一份班級刊物，包含封面、扉頁、目錄、插圖頁、附錄、封底等部分，可以在列印後直接裝訂成冊嗎？
PowerPoint呢？你有沒有研究過蘋果公司發佈會上那些幻燈片的設計？當約伯斯（多年以前）或蒂姆·庫克站在幻燈片前的時候，他們的演講思路是如何與幻燈片完美結合的？
還有哦，別忘了學學如何為數碼照片做後期，如何用電腦或手機剪視頻，如何為剪輯好的視頻配字幕，如何將照片、音樂、視頻等素材結合起來，做出一段吸引人的快手/抖音短視頻。
最後，抽空玩玩那些設計精妙的遊戲吧，比如《紀念碑穀》、《塞爾達傳說：曠野之息》之類；同時，遠離那些滿屏廣告，或者一心騙你在遊戲裡充值花錢的垃圾。
【問題103】休閒模式 | 不學學知識嗎？
當然要學知識。下面每種實用的電腦知識都夠大家學一陣子了。
（1）色彩知識：你知道同一張數碼照片在不同品牌的手機螢幕上、不同的電腦螢幕上、不同的智慧電視上顯示時，為什麼經常有較大色差嗎？你知道有一些色彩只適合螢幕顯示，不適合列印輸出嗎？你知道軟體工具裡常用的RGB、HSL之類的色彩空間都是什麼意思嗎？如何在設計PowerPoint幻燈片時選擇一組和諧美觀的色彩？
（2）字體知識：你知道什麼是襯線字體，什麼是無襯線字體嗎？你知道網頁中常用的英文字體都有哪些嗎？你知道商務演講時最適用于幻燈片的英文字體有哪些嗎？你知道電腦和手機常用的黑體、宋體、仿宋體、楷體等中文字體分別適合哪些實際應用場合嗎？你會將不同字體混排成一個美觀的頁面嗎？
（3）網路知識：你知道5G是什麼嗎？你知道5G和4G在通信頻寬、通信距離上的具體區別嗎？你知道什麼是路由器，什麼是防火牆嗎？你知道如何配置路由器，如何配置防火牆嗎？微信或QQ聊天時，對方發的文字、語音或視頻是如何傳送到你的手機上的？
（4）應用知識：淘寶中搜索得到的商品資訊是從哪裡來的？商品是按什麼方式排序的？為什麼購物APP經常會推薦給你一些曾經買過、看過的商品？你知道如何為自己建立個人網站嗎？你知道如何管理微信公眾號嗎？
（5）安全知識：你知道網路上的釣魚攻擊是怎麼回事兒嗎？你知道什麼是電腦漏洞嗎？你知道駭客為什麼想把一大批受攻擊的電腦變成可以遠端操控的傀儡機嗎？你知道為什麼現在很多手機APP都要通過短信發送驗證碼嗎？如果驗證碼被壞人截獲，你會面臨哪些風險？
這裡只是舉例。實用的電腦知識還有很多。大家可以自己發掘。
【問題104】休閒模式 | 我需要學程式設計嗎？
可以學，但不是必須。即便學，也只需要根據自己的需要，學那些最能幫你解決現實問題的部分。
【問題105】休閒模式 | 我該學什麼程式設計語言？
在“休閒模式”裡，電腦就是工具，程式設計也是工具，夠用就好。學什麼程式設計語言，完全看你想要電腦幫你做什麼。
• 如果你想對資料處理有更多自主權，那不妨學學Python；
• 如果你想做簡單的交互演示程式，那就先把JavaScript學起來；
• 如果你想更好、更快地寫論文，那不妨學學LaTeX（什麼什麼，LaTeX不是程式設計語言？你太小看LaTeX了）；
• 如果你想學做簡單的手機APP，那麼，Android手機就學Java，蘋果手機就學Swift好了；
• 如果你只想知道程式設計是怎麼回事，那……從Python或JavaScript開始就行。其實，跟五六歲的小朋友一起學學Scratch圖形程式設計也不錯。
【問題106】休閒模式 | 我需要學人工智慧嗎？
在“休閒模式”裡，最需要學的不是“人工智慧的實現原理”，而是“什麼是人工智慧”，以及“人工智慧能做什麼，不能做什麼”。
• 在手機上試一試，人工智慧做語音辨識時能做到什麼水準？哪些話容易識別，哪些話不容易識別？
• 打開機器翻譯軟體，試一試哪些資訊翻譯得好，哪些資訊翻譯得不好？
• 手機上的拍照軟體一般都有人臉識別功能。試一試人臉識別在什麼場景下做得好，什麼場景下做得不好？
• 找一部講人工智慧的科幻電影，用自己的判斷解讀一下，電影裡哪些技術有可能成為現實，哪些技術存在邏輯矛盾。
【問題107】休閒模式 | 推薦什麼參考書、參考文獻？
書不重要，豆瓣評分7分以上的電腦應用、程式設計甚至科普類圖書都可以拿來翻翻。
直接在知乎裡搜索你想瞭解或學習的知識點可能更有效率。
如果你意猶未盡，覺得自己剛活動開筋骨，還想挑戰更高層次，歡迎進入“探險模式”。⟹請跳轉至【問題200】
否則，“休閒模式”到此結束。⟹請離開此問答
【問題200】探險模式 | 主要學什麼？
“探險模式”需要有挑戰精神。電腦科學的世界技術演進快，脈絡複雜，要想在探索時不迷路，你得通過有順序、有系統地學習電腦知識，慢慢構建出一張可以在未來幫你走得更遠的思維地圖來。
在“探險模式”裡，電腦就不止是一件能快速計算的工具了。電腦更像是我們大腦的一種延伸。這既包括認知能力的延伸，也包括認知邏輯的延伸。隨著學習深入，大家會逐漸體會到電腦所具有的多維度能力：
電腦是一種可以表示不同類型資訊（數、符號、文字、語音、圖像、視頻、虛擬空間、抽象邏輯）的“資訊管理機”；
同時，電腦也是一種可以連續執行指令以完成特定的資訊處理任務的“指令處理機”；
同時，電腦還是一種可以在知識與邏輯層面完成特定推理任務的“知識推理機”；
同時，電腦也是一種可以從人類給定的資料或自我生成的資料中總結規律，建立模型，自主完成某些決策的“智慧學習機”。
“探險模式”的目標就是盡可能準確地認識電腦，掌握有關電腦運行的最基本規律。有了這些基礎。未來在大學期間或工作中，你就能更容易地設計電腦軟硬體系統，或是設計出碳基大腦（人類）與矽基大腦（機器智慧）之間的最佳協作方案。
【問題201】探險模式 | 我的英語水準足夠嗎？
蘋果每年秋季的新品發佈會，不加字幕的話，你能聽懂多少？
能聽懂大部分：建議在學習電腦的過程中，盡可能使用英文教材、英文文檔。
能聽懂小部分：建議將原來準備學電腦的時間，分出一部分來學英語。
只能聽懂“你好”“再見”之類：⟹請離開此問答。然後，把原來準備學電腦的時間用於學英語，六個月後再回來。
【問題202】探險模式 | 我的數學水準足夠嗎？
如果你是數學和數學應用小能手——較複雜的數學問題總能快速找到核心思路，或快速簡化為簡單問題；很容易就能將抽象概念映射到具體的數學圖形，或將數學問題與相應的現實問題關聯在一起：請繼續探險之旅。
如果你應付正常數學課程感到吃力：建議將原來準備學電腦的時間，分出一部分來學數學。
如果你還搞不清楚什麼是方程、函數、集合、概率……：⟹請離開此問答。然後，把原來準備學電腦的時間用於學數學，六個月後再回來。
【問題203】探險模式 | 為什麼強調英語和數學？
（1）統計上說，最好的電腦參考資料大都是英文寫的，最好的電腦課程大都是用英文講的，最新的電腦論文大都是用英文發表的。
（2）函數、方程、坐標系、標量、向量、排列組合、概率這些中學數學裡會初步學習到的數學知識，是電腦科學的基礎。
【問題204】探險模式 | 電腦知識那麼多，正確的學習順序是什麼？
最重要的順序有兩個。建議先從順序一開始，學有餘力時兼顧兩個順序。
順序一：自底向上，即，自底層原理向上層應用拓展的順序。
電腦原理的基礎知識：
為什麼每台電腦（包括手機）都有CPU、記憶體和外部設備？
（馮·諾依曼體系結構的）記憶體中為什麼既可以存儲資料，也可以存儲指令？
CPU是如何完成一次加法運算的？
程式設計語言的基礎知識：
資料類型，值，變數，作用域……
語句，流程控制語句……
過程、方法或函數，類，模組，程式，服務……
編譯系統的基本概念：
電腦程式是如何被解釋或編譯成目標代碼的？
演算法和資料結構的基礎知識：
陣列，向量，鏈表，堆，棧，二叉樹，樹和圖……
遞迴演算法，排序演算法，二叉樹搜索演算法，圖搜索演算法……
應用層的基礎知識：
為什麼電腦需要作業系統？設備驅動程式是做什麼的？
網路通信的基本原理是什麼？流覽器是怎麼找到並顯示一個網頁的？
資料庫是做什麼用的？
虛擬機器是怎麼回事？
人工智慧系統的基礎知識：
先熟悉些線性代數、概率和數學優化的基礎知識。
什麼是機器學習？從簡單的線性回歸中體會機器學習的基本概念、基本思路。
什麼是神經網路？什麼是深度神經網路？為什麼神經網路可以完成機器學習任務？
如何使用PyTorch或TensorFlow實現簡單的深度學習功能？
順序二：自頂向下，即，自頂層抽象邏輯向下層具體邏輯拓展的順序。
• 電腦的本質是什麼？
• 什麼是圖靈機？什麼是通用圖靈機？
• 什麼是讀取﹣求值﹣輸出迴圈（Read–eval–print Loop，REPL）？
如何用自頂向下的方式理解（解析、解釋、編譯）一段程式碼？
• 靜態語言和動態語言的區別？
如何理解變數與資料類型之間的綁定關係？
• 什麼是函數式程式設計？
程式設計語言中，函數的本質是什麼？
函數為什麼可以像一個值一樣被表示、存儲、傳遞和處理？
• 什麼是物件導向？
類的本質是什麼？
如何用物件導向的方式定義個功能介面？
如何依據介面實現具體功能？
• 什麼是事件驅動？
什麼是事件？事件如何分發到接收者？
如何在事件驅動的環境中理解代碼的狀態和執行順序？
【問題205】探險模式 | 如何提高程式設計水準？
在掌握基本知識體系的基礎上，學好程式設計只有一條路：多程式設計，多參加程式設計比賽，多做程式設計題，多做實驗項目，多找實習機會——其中，能參與真實專案是最有價值的。
【問題206】探險模式 | 該從哪一門程式設計語言學起？
我個人推薦的程式設計入門語言（可根據情況任選）：
Python
Java
Swift
C#
JavaScript / TypeScript
Ruby
……
可能不適合入門，但適合後續深入學習的語言：
C
C++
Go
Objective-C
組合語言
機器語言（CPU指令集）
Shell Script
Lua
Haskell
OCaml
R
Julia
Erlang
MATLAB
……
【問題207】探險模式 | 如何選參考書和參考資料？
（1）強烈推薦的參考書和參考資料：
• MIT、Stanford、CMU、UC Berkeley這四所大學中任何一個電腦專業方向使用的教學參考書或參考資料。網上可以查到這些學校電腦專業方向的課程體系，有的學校甚至公開了課程視頻。其中往往會列舉參考書和參考資料連結。
• 維琪百科（英文）上的數學、電腦科學相關條目。
• Github上star數在1000以上的開原始程式碼和開來源文件。
（2）強烈推薦但須小心辨別的參考資料：
知乎上的數學、電腦科學相關條目。使用時需要格外注意三件事：
儘量只看高贊答案或高贊文章；
辨別並避開廣告軟文；
辨別並避開純抖機靈的故事或段子。
Stack Overflow上的程式設計問題解答：
自己動手實驗，辨別解答是否有效。
CSDN上的程式設計問題解答：
自己動手實驗，辨別解答是否有效。
（3）其他推薦的參考書和參考資料：
國內專業作者寫作的專業技術書籍（豆瓣評分7分以上的）。
大廠（Google、Facebook、Microsoft、Amazon、阿裡、騰訊、百度、頭條等）資深工程師的技術公號、專欄、博客等。
著名圖書系列：如O’Reilly的動物封面的系列圖書（請注意最新版本和時效性）。
國內翻譯的著名技術圖書（譯本在豆瓣評分7分以上的）。
（4）儘量避免的參考書和參考資料：
• 已經過時的圖書或參考資料。
• 作者或譯者人數比章節數還多的專業圖書。
• 百度百科上的數學或電腦科學相關資料。
什麼什麼？你這篇問答居然沒有推薦一本具體的圖書？是，沒錯。如果你覺得即便有了上面的線索，自己還是找不到好書好資料，那也許你還是適合“休閒模式”⟹請跳轉至【問題100】
遞迴迴圈效率 在 Re: [問題] 關於遞迴加快速度的迷思？ - 看板C_and_CPP 的推薦與評價
※ 引述《crazycat2 (浪無定所)》之銘言：
<deleted>
: 但因使用方式，還是以遞迴為主。
: 不經好奇若將遞迴改成static或是marco會更快嗎？
最近也對遞迴有些疑惑, 趁此機會來跟大家討教一下, 以下是我自己的觀點跟想法:
遞迴與迭代這兩個觀念可以在三個層次上遇到：
1. 抽象層次: 遞迴關係 (recurrence) 與迭代關係 (iteration)
2. 語言層次: 遞迴函式呼叫 (recursive function call) 與迴圈 (looping)
3. 底層實作: 呼叫 (call) 與跳躍 (jump) [一般呼叫的實作會包括跳躍]
其中這三個層次有一個直觀的串連關係。例如, 如果有一個題目在抽象層次具有遞迴關
係, 我們就可以依照該遞迴關係去寫語言層次的遞迴函式並呼叫他。這遞迴函式呼叫在
編譯時, 編譯器可以直觀的使用底層呼叫 (call) 類的指令去實作。遞迴關係、遞迴函
式呼叫與底層呼叫這三個不同層次的詞可以有這樣一個直觀的串連關係。相對地，迭代
關係、迴圈與跳躍也可以發現有類似的串連關係。只是這些串連關係並不具有強制性，
像是迴圈也可以用來實作遞迴關係，跳躍也可以用來實作遞迴呼叫，只是可能會有一些
其他的限制或多餘的步驟。不過大致上我們可以具有一個選擇的標準：我們希望在語言
層次可以寫簡短且容易了解維護的程式碼, 同時希望在編譯後於底層實作上具有高的運
作效率。
首先，要認知在這樣的前提上，已經接受在抽象層次上我們要解決的題目是具有直觀的
遞迴關係的，要不然我們沒必要討論這個問題 (就不要用遞迴就好)。 常見的例子像是
要求得 Fibonacci 數列中某項的值。Fibonacci 數列最直觀的定義就是使用遞迴關係
來表示:
f(n) == f(n-1) + f(n-2), (n > 1) [遞迴關係]
f(n) == n , (n <= 1) [邊界條件]
因為具有遞迴關係，所以在語言層次上我們依照這樣的遞迴關係去定義一個遞迴函式並
呼叫是再直觀不過的實作方法：
int f(int n) {
if (n <= 1) return n; // [邊界條件]
else return f(n-1) + f(n-2); // [遞迴關係]
}
但是我們也知道 Fibonacci 數列中每一項的值可以使用迴圈型的演算法算出，因為遞
迴關係可以反向地看成是迭代關係：
n == f(n) , (n <= 1) [初始條件]
f(n-1) + f(n-2) == f(n), (n > 1) [迭代關係]
所以當我們說『遞迴的效率比迴圈差』這個論述時，指的是在語言層次使用遞迴函式呼
叫實作會比使用迴圈實作效率要來得差，而不是說具有遞迴關係的題目本身就象徵著效
率不會好。
那為什麼在語言層次使用遞迴函式呼叫實作感覺上會比使用迴圈實作差？
最常見的範例就是跟計算 Fibonacci 數列的某項值時一樣，遞迴函式呼叫時會『重複』
呼叫具有相同參數值的同名函式。例如要計算 f(10) 時， f(8) 就會在計算 f(10) 跟
f(9)時都被呼叫並重新計算一次。這個會造成效率指數性的下降，也就是我們直觀地使
用遞迴函式呼叫去實作遞迴關係時踩到的效率陷阱。
那為什麼迴圈會是擺脫這個效率陷阱的救星呢？
// 下面的程式碼為了做好的對應，我並沒做最簡化
// 如果要求取 f(10) 的值:
int main() {
int F[10+1];
for (int i = 0; i <= 10; ++i) {
if (i <= 1) F[i] = i;
else F[i] = F[i-1] + F[i-2];
}
// 此時 F[10] 的值就是我們要的 f(10) 的值
printf("%d\n", F[10]);
return 0;
}
這個迴圈確確實實不多不少執行了 10+1 次，看起來要比使用遞迴函式呼叫少執行了很
多次計算 (因為我們沒有重複計算到) 。但是關鍵其實是因為這裡偷偷做了一個類似快
取的機制 (空間換取時間)。也就是說，我們也可以依樣畫葫蘆地把遞迴函式呼叫改成:
int f(int n, int *F, bool *visited) {
if (visited[n]) return F[n];
visited[n] = true;
if (n <= 1) {
F[n] = n;
} else {
F[n] = f(n-1, F, visited) + f(n-2, F, visited);
}
return F[n];
}
int main() {
int F[10+1];
bool visited[10+1] = {};
printf("%d\n", f(10, F, visited));
return 0;
}
我們維持了語法中的遞迴函式呼叫機制，並且通過類似快取的機制避免了重複計算，但
是也必須為此付出一些代價：我們需要記錄是否已經計算過 (visited)。但是相對地，
為什麼迴圈可以不用跟這裡一樣要付出記錄的代價？原因是因為遞迴關係如果要有解 (
也就是遞迴函式呼叫如果要確定能夠結束) ，那所有遞迴函式的呼叫可以依照呼叫者跟
被呼叫者的關係畫成一個樹的結構。我們只要確保在樹枝中比較接近樹葉的函式呼叫比
比較接近樹根的函式呼叫先計算，那最後的結果就會正確。也就是說，我們可以將他寫
成迴圈形式而不用記錄執行過哪些函式是因為存在一個計算的順序可以確保過程中被呼
叫者的值會比呼叫者先被算出來。例如只要確保迴圈中 f(6) 比 f(7) 跟 f(8) 先求出
就可以了。
那遞迴函式呼叫難道就不能做嗎？顯然不是：
void f(int n, int *F, int i = 0) {
if (n < i) return;
if (i <= 1) F[i] = i;
else F[i] = F[i-1] + F[i-2];
f(n, F, i+1);
}
int main() {
int F[10+1];
f(10, F);
// 此時 F[10] 的值就是我們要的 f(10) 的值
printf("%d\n", F[10]);
return 0;
}
(確實有更簡單的方式來寫這個題目，不過跟這裡要討論的差異無關就不細寫。)
如果這樣寫的話，在語言層次，我們保留了遞迴函式呼叫的機制，但似乎有一些多餘的
代價，只是並不那麼地明顯，至少直觀上沒有顯著會慢很多的理由。此時我們可以開始
討論底層實作的層面。在具有遞迴函式呼叫的程式碼經過編譯器編譯後，一般的硬體結
構要實作呼叫 (call) 會比單純的跳躍 (jump) 要複雜，簡單的理由就是每次呼叫要記
得回傳時回來的位址，還有要儲存目前函式內部變數的狀態，以免到時回傳回來後原本
的資料都遺失了。因為這種遞迴的形式是將遞迴呼叫放在遞迴函式定義的最後一行 (且
只有一次)，也就是所謂的尾端遞迴 (tail recursion) 或尾端呼叫 (tail call) 。事
實上我們不必去儲存每次呼叫回傳時要回來的位址，因為最後回傳時都會經過一連串的
回傳後回傳到第一個呼叫者，所以我們只需要記得第一個呼叫者的位置。同時我們也不
用在呼叫後還儲存著目前函式內部變數的狀態，因為回傳回來後除了繼續回傳回去也不
會做任何事。
現代的編譯器在你適當的表示成上述尾端呼叫的程式碼時，可以幫你做尾端呼叫最佳化
(tail call optimization)，避免在底層實作時使用呼叫 (call) ，所以原則上可以做
到跟迴圈幾乎無差別的效率。甚至如果你迴圈寫得不好 (例如不良的使用迭代器)， 反
而寫得好的遞迴會比較快。
以上是假設遞迴關係本身是獨立的計算，不牽涉到外部操作 (例如使用 cout)，也就是
我們不用去保證不同樹枝之間呼叫的先後關係。這在實務上其實很少遇到，一般我們遇
到的是像漢諾 (Hanoi) 塔這類的遞迴關係，也就是遞迴函式執行的順序會影響最後的
結果。所以為了保證執行順序，在使用迴圈實作遞迴關係時，我們會需要使用類似堆疊
的結構來模擬，此時遞迴跟迴圈的效率優劣就更難說，反而會與你是否有好好的寫程式
碼有比較大的關係。此外，用迴圈實作遞迴關係是在我們對於參數值有個好的順序 (例
如從 0 算到 10) 的情況下，才容易使用類似快取的機制。如果參數空間太大，而實際
上使用的參數值組合不多，快取機制會更難做而沒效率。不過這都是後話, 我想我有空
再補完.....
結論，在語言層次實作遞迴關係時用遞迴函式呼叫跟迴圈哪個方式好還是跟你的寫法和
編譯器有關。用迴圈實作會 "大幅地" 改進效率通常是因為我們偷偷在其中增加了其他
機制與特性，而這些機制與特性其實遞迴函式呼叫也都可以用只是你沒用，也就是你用
了一個比較聰明的方法去欺負一個比較簡單的方法。
--
寫一寫發現好像大部分是常識, 我錯了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.217.49
... <看更多>