為什麼函數能遞歸調用自己？

01-02

在定義遞歸函數的時候，往往還沒有定義完函數，就會自己調用自己，只是改變一下參數。我想請問，為什麼一個函數還沒有定義完全就能調用它了呢？程序設計語言是怎麼實現這一點呢？至少我知道如果一個數據結構或者類沒有定義完，是不能使用它的啊，因為無法分配內存。但是函數為什麼就可以呢？

首先你要理解函數調用的本質:

1.保存當前指令地址

2.跳轉到被調用函數(指令段)的起始地址

實際過程比這個複雜, 比如還包括保存臨時變數和傳參等等, 但是對我們正在討論的問題不起到本質影響所以省略掉不談

函數調用並不是在原地展開代碼

每一個函數都是一段獨立存在於存儲器中的指令序列

每個程序的內存空間中都包括一個叫做"棧(stack)"的區域, 它的特點是先進後出, 就像一摞書, 只能往頂端放書, 也只能從頂端取書

每當你調用一次函數, 就會向棧中壓入(push)返回地址, 當函數返回(return)時從棧中彈出(pop)返回地址並跳轉回返回地址.

所以, 自身調用乃至循環調用形成的遞歸調用在進行時, 就會不斷壓棧來保存函數運行狀態, 當遞歸一層一層返回時, 則是不斷出棧了

實際過程和這個有出入, 但是本質是一樣的, 你可以通過學習一門彙編來對這個過程總結出自己的理解

嗯，知道類，事情就好辦了。

class A ｛

A a；

｝；

這樣是不行的

class A ｛

A* a；

｝；

這樣是可以的。

為什麼呢，因為對象需要知道大小，但是指針大小是固定的。

函數的調用，就是跳轉到一個函數的入口地址，知道參數就足夠了，不涉及到內存分配。

詳情見編譯原理

定義時並沒有調用自己，運行時才調用，你說的矛盾並不存在

有時確實是個問題，取決於調用機制的設計。

比如，如果函數體所用內存是caller分配的，或者參數/返回值類型是在函數體里推導的，為了處理遞歸就有可能需要多走一個pass。

C家族的語言會在設計上規避這些情況，在確定函數原型的時候就能確定調用方式了。

壓棧，跳轉，壓棧，跳轉，壓棧，跳轉。。。。。。

出棧，跳轉，出棧，跳轉，出棧，跳轉。。。。。。

函數在調用自己以前已經告訴編譯器了，他自己叫xxx，參數有xx。函數名xxx是個指針，指向函數在內存中的起始位元組處，在後面調用自己遞歸，其實就是一遍一遍的在執行內存中的同一部分代碼，每次調用會保存現場到棧裡面去。只要遞歸本身是收斂的，最後函數總能執行到return，然後就再從堆棧里讀出以前的現場，倒著算回來。

其實樓上已經有人列出了類的自引用，相當於C語言裡面的自引用結構體。一個結構體包含自身是非法的，但一個結構體包含自身的指針並不非法。C語言裡面的指針佔用空間是固定的(四個位元組)，所以編譯的時候分配內存單元並不會引起問題。

函數調用時保存現場，然後把函數參數放到CPU寄存器里，再把函數地址給SP指針，之後CPU自動就去按SP指針去逐行讀內存代碼執行去了。

這個地方的函數調用，和上面的結構體自引用類似。

我只學過C語言和一些微機原理，如果理解有錯誤，請指出，謝謝。

去看看彙編

很多從機器碼的角度來解釋的答案很好。這裡說另外一個角度，也是bhuztez沒有用大白話點出來的：函數遞歸調用自己依靠延遲求值。

函數定義裡面調用其它函數或遞歸調用，都只需要一個名稱，實際上不需要馬上求值。調用函數時運行到這個點才需要求值。函數式編程有一種技巧，當不想馬上求出函數f的值時，可以用"( f ) 或者lambda x . f 來代替。需要求值時再計算f的值。程序後面調用函數時，運算到函數內部遞歸調用的位置，才需要把遞歸調用的那個函數求值。同樣，也可以想像成把前面包裝的lambda表達式求值。這樣，函數通過延遲求值的策略，實現了遞歸調用。用機器碼的語言來說，定義函數時只是標記了這裡要調用的函數的地址。函數遞歸調用增長一層時，寄存器壓棧，開闢新棧幀，進入被調用函數的地址，這樣就遞歸調用了自己。定義函數和調用函數是兩個過程。函數定義時，任何變數、函數都只是名稱而已。只有到運行時，才需要從上下文環境中得到變數或函數的「真實身份」。

回到在letrec方式下定義的遞歸函數，letrec f =M in N，計算為(fix lambda f. M) 代入N中求值。求值時有 fix F = F ( fix F )，後面括弧中的fix F就是作為一個暫時不求值的實參，傳送到F中求值，其餘部分計算完後然後才繼續對內部的fix F再展開。

附帶說lazy evaluation。急切規約的情況下，無法直接求值遞歸函數，會導致發散。所以積極規約的規則下求遞歸函數，定義函數時要用delay把遞歸調用的函數包裝一層，調用時再按需求值。這與一般語言中定義遞歸函數的做法是暗合的，即把函數遞歸調用處理為一個符號。

因為我自己調用自己時只要返回值和參數表，具體的函數體在執行時才用得到。

突然想到題主是不是想問Y-combinator那個東西

函數式編程裡面確實會遇到題主所說的那個問題，所以需要通過一些奇怪的技巧來解決掉

推薦一篇文章

http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/

--------------------------------------------------------------然而。。。代碼難道不是應該寫完後執行么。。。

有沒寫完就能執行的？

函數調用其實是一個goto語句，所以遞歸其實就是循環。

然後為了方便，大家規定了一些固定內存位置存放參數，這樣的話，代碼A代碼B代碼C都可以用自己的方法初始化參數再調用goto函數F。

這些參數當中，包括了代碼ABC各自起點的內存位置，這樣，函數F在運行完之後就能跳回代碼ABC，而不會跳錯。

用這個思路理解一下就明白了。