Tailing Recursion and its variation

Tailing Recursion是大部分Function Language的基本配備，在沒有迴圈的情況下，Recursive是唯一的方案。
而Tailing Recursion是Tail Call的一種特例。只是最後呼叫的函數是自己。
在不討綠用公式解跟迴圈解的情況下，要從1加到1000000000我們會這麼寫。

long long sum(int n)
{
	if (n == 0) return 0;
	return n + sum(n - 1);
}
cout << sum(1000000000) << endl;

這段程式在Visual C++會掛，而在GCC跟Clang可以正常運作。 (Visual C++的判別還真有點弱)。
不過我想說的是後面這個，Tailing Recursion Optimization。
跟上面很類似，不過會多帶一個參數，代表初始狀態。
上面的範例可以重新寫成

long long int sum(int n, long long int v)
{
	if (n == 0) return v;
	return sum(n - 1, n + v);
}
cout << sum(1000000000, 0) << endl;

這種寫法比上面好的點，在於當我們要做Recursive呼叫的時候，必須保留呼叫時每一層的狀態，存在Stack裡，當你遞迴深度過深時，超過OS給予的極限，就會造成Stackoverflow。而用下面這種寫法的話，則不需要保留遞迴中的堆疊。只需要修改當前堆疊的值，然後既需呼叫函式即可。

還有如果把之後要做的事情當做參數傳進來，就變成Continuation-passing style了。

把程式碼改寫成這樣

void sum(int n, long long int v, function<void (long long)> contWith)
{
	if (n == 0) return contWith(v);
	return sum(n - 1, n + v, contWith);
}
sum(1000000000, 0, [] (long long v) { cout << v << endl; });

結果所有編譯器全掛了，同樣邏輯的程式碼用Haskell重寫一次

1
2
3

sum' n total cont  
    | n == 0 = cont(total)
    | otherwise = sum' (n - 1) (total + n) cont

整個計算資源被耗盡了，難道1000000000真的玩太大了。