程序的函數副本是個什麼概念？

在一本數據結構的書上看到一句話「大量的遞歸調用會建立函數的副本，會耗費大量的時間和內存。」沒能找到相應的答案。我想請教一下，1.函數副本是什麼？2.函數的執行是怎樣的過程？

---

1. 漆黑的電影院里，坐在你旁邊的女神突然問道：「我們這是第幾排？」

2. 你也不知道，於是拍拍坐在你前面的路人甲：「不好意思，你這是第幾排？」
3. 路人甲也不知道，於是拍拍坐在他前面的路人乙：「不好意思，你這是第幾排？」
4. 路人乙也不知道，於是拍拍坐在他前面的路人丙：「不好意思，你這是第幾排？」
5. 路人丙也不知道，於是拍拍坐在他前面的路人丁：「不好意思，你這是第幾排？」
6. 路人丁也不知道，於是拍拍坐在他前面的路人戊：「不好意思，你這是第幾排？」
7. 路人戊也不知道，於是拍拍坐在他前面的路人己：「不好意思，你這是第幾排？」
8. 路人己也不知道，於是拍拍坐在他前面的路人庚：「不好意思，你這是第幾排？」
9. 路人庚也不知道，於是拍拍坐在他前面的路人辛：「不好意思，你這是第幾排？」
10. 路人辛也不知道，於是拍拍坐在他前面的路人壬：「不好意思，你這是第幾排？」
11. 所幸這位老兄知道，於是回答道：「哦，我這是第三排。」
12. 路人辛鬆了一口氣，回頭對路人庚說：「哦，我這是第四排。」
13. 路人庚鬆了一口氣，回頭對路人己說：「哦，我這是第五排。」
14. 路人己鬆了一口氣，回頭對路人戊說：「哦，我這是第六排。」
15. 路人戊鬆了一口氣，回頭對路人丁說：「哦，我這是第七排。」
16. 路人丁鬆了一口氣，回頭對路人丙說：「哦，我這是第八排。」
17. 路人丙鬆了一口氣，回頭對路人乙說：「哦，我這是第九排。」
18. 路人乙鬆了一口氣，回頭對路人甲說：「哦，我這是第十排。」
19. 路人甲鬆了一口氣，回頭對你說：「哦，我這是第十一排。」
20. 你鬆了一口氣，回頭對女神說：「我們這是第十二排。」

前面這個活動中，除了女神外，每個人都在干同一件事：

告訴別人你自己在哪一排：

　　如果 你知道自己是第幾排，就直接回答就行了

　　否則 先問你前面的人他在第幾排，他回答說第幾排，你就回答他的排數加一。

如果「這件事」是個函數，那麼「某人在干這件事」就是這個函數的副本：

• 步驟 1 完成時，只存在 1 個副本（你）
• 整個活動在步驟 11 達到高潮，此時一共存在 10 個副本
• 到了步驟 12，路人壬已經完成了使命，此時就只存在 9 個副本了

函數的執行：

1. 記下拍你肩膀的人，待會兒要把答案告訴他（返回地址）
2. 記下問的是啥（參數）
3. 知道就直接回答，不知道就先問前面的人再回答（執行函數體）
4. 把答案告訴拍你肩膀的人（把返回值放到約定的地方，跳到返回地址開始執行）

5. 回到什麼都沒發生的時候的狀態，繼續看電影

p.s. 你坐得越靠後，整個活動中牽扯到的人就越多，你不覺得不好意思嗎？（即題目中的「浪費內存」）

---

占坑。一會來答

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

函數的執行， 是將當前寄存器的狀態保存在棧中，然後跳到函數地址執行函數指令的過程。

例如在mips指令集中，調用一個函數

int f(int a)
{
a++;
return a;
}


彙編指令是執行了這樣一個過程

（mips中$a0~$a3是參數寄存器，$v0,$v1是返回值寄存器，$s0~$s7是通用寄存器，$t0~$t9是臨時寄存器，$ra是返回地址的寄存器,$zero是0寄存器）

假如當前a存在寄存器$s0中

add $a0, $s0, $zero #將a賦值到a0作為參數傳遞
jal f #跳傳到函數f的入口地址並將返回地址保存在$ra中
addi $sp, -4 #調整棧指針，因為此函數有一個4位元組的參數，因此棧指針下調4
#假如函數體中定義了其他的棧變數，這裡作相應下調
sw $a0, 0($sp) #將參數入棧進行保護，若函數體中定義了其他的棧變數，這裡也進行入棧
addi $a0, $a0, 1 #執行函數體
add $v0, $a0, $zero #將結果送入返回值寄存器
lw $a0, 0($sp) #將參數寄存器恢復原值，即從棧中讀取
addi $sp, 4 #調整棧指針
jr $ra #返回


（呼排版真費勁。）

因此，調用函數是在棧中不斷的申請空間。調用一個遞歸函數時，每調用一次，就在棧中申請一次空間，並同時產生函數的一個副本。而此時之前的函數調用還沒有完成，棧空間沒有釋放，就導致了使用了大量的棧空間，即耗費了大量的內存。又因為內存操作相對寄存器操作cost非常大，耗費了大量的時間。

解決這個問題的辦法有二

一是將遞歸改寫為循環，這個就不再說明

二是將遞歸改寫為尾遞歸，可見尾調用

---

大量的遞歸調用會建立函數的副本

=========================

我覺得這話說得太武斷了

事實上不一定會發生這種情況

---

推薦閱讀：