Scala的遞歸，溢出

Question

這裏是2層的功能：

def Foo1(s: ((BigInt, Long) => Long) 
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo1(s)) 

def Foo2(s: (=> (BigInt, Long) => Long) 
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo2(s)) 

當它們被稱爲使用以下參數：

Foo1(rec => (x, s) => 
      if (x == 1) s 
      else rec(if (x % 2 == 0) x/2 else 3 * x + 1, s + 1))(56, 0)  
Foo2(rec => (x, s) => 
      if (x == 1) s 
      else rec(if (x % 2 == 0) x/2 else 3 * x + 1, s + 1))(56, 0) 

第一導致堆棧溢出，並且第二正常執行。

此外，這個表達式是什麼意思：(=> (BigInt, Long) => Long)？

Answer 1

簽名(=> (BigInt, Long) => Long)表示按名稱參數，是瞭解爲什麼Foo2不會溢出堆棧的關鍵。

在Scala中理解函數的方法是將參數替換爲函數的定義。然後在評估參數時重複替換。我們還必須認識到s在兩個不同的地方使用，一個作爲Foo函數的參數，另一個作爲未命名函數中的參數傳遞到Foo。

評估第一函數調用結合參數s到

rec => (x, s) => if (x == 1) s else rec(if (x % 2 == 0) x/2 else 3 * x + 1, s + 1)

果然rec成的兩個參數，一個BigInt和Long遞歸函數。

然後您評估Foo1，將s（外部）的表達式替換爲s(Foo1(s))。這產生：

(rec => (x, s) => 
      if (x == 1) s 
      else rec(if (x % 2 == 0) x/2 else 3 * x + 1, s + 1)) (Foo1(rec => (x, s) => 
      if (x == 1) s 
      else rec(if (x % 2 == 0) x/2 else 3 * x + 1, s + 1)) 

然後，您需要評估Foo1，傳遞它的功能。這將繼續遞歸直到您用完堆棧空間。另一方面，使用按名稱調用語法而不是按值調用，因此在參數(56, 0)實際綁定之前，不需要執行第二階段的評估。