今天重新看了下文中最後的實現代碼，感覺還是不夠滿意：因為引入了一個對用戶來說不是很必要的數據結構RecFunc<>，用戶需要定義的代碼大概是這樣：
(rec,i,n,a,b) => (n<3 ? 1 : (i==n ? a+b : rec.Callback(i+1, n, b, a+b)))
從調用方的角度來看，下面代碼就比上面的更容易理解（不用self都不好意思說自己學過python）：
(self,i,n,a,b) => (n<3 ? 1 : (i==n ? a+b : self(i+1, n, b, a+b)))
是不是該將那個類繼承自Delegate？可是C#不許直接繼承這個特殊類。或許可以用Delegate.CreateDelegate創建一個委托對象來組合？順著這個方向，進而想到了直接創建一個匿名委托來實現。
於是我將代碼重新修改了下，短小精悍了不少，最終尾遞歸包裝的代碼如下：
public static Func<T1,T2,T3,T4,TResult> TailRecursive<T1,T2,T3,T4,TResult>
(Func<Func<T1,T2,T3,T4,TResult>,T1,T2,T3,T4,TResult> func)
{
return (p1,p2,p3,p4) =>
{
bool callback = false;
Func<T1,T2,T3,T4,TResult> self = (q1,q2,q3,q4) =>
{
p1 = q1;
p2 = q2;
p3 = q3;
p4 = q4;
callback = true;
return default(TResult);
};
do
{
var result = func(self,p1,p2,p3,p4);
if (!callback)
{
return result;
}
callback = false;
} while (true);
};
}
另外還補充了普通遞歸的包裝方法：
public static Func<T1,T2,T3,T4,TResult> Recursive<T1,T2,T3,T4,TResult>
(Func<Func<T1,T2,T3,T4,TResult>,T1,T2,T3,T4,TResult> func)
{
Func<T1,T2,T3,T4,TResult> self = null;
self = (p1,p2,p3,p4) => func(self,p1,p2,p3,p4);
return self;
}
寫完代碼，自然還是要測試下的，我測試對比了三種方式的計算Fib數列的性能：(1)最基本的遞歸調用的方式(2)用上面的Recursive<> (3)用上面的TailRecursive<>尾遞歸。
前兩種都屬於普通遞歸，受到調用棧的限制Fib(10000)還可以執行，但是Fib(20000)就堆棧溢出了。第三種方法由於是尾遞歸，調用Fib(20000)自然沒問題，就是Fib(10000000)也是瞬間執行完。
測試總要有數據支持才行，剛剛的測試發現，前兩種方法Fib(10000)時Stopwatch記錄的毫秒數都是0，無法根據花費時間來比較三者的性能。於是我又加了段很邪惡的測試代碼，白白浪費CPU時間：
// 外部初始化
int x = 10000;
var s = x.ToString();
// 遞歸循環中
x = -x;
for (int j = 0; j < Math.Abs(x); j++)
{
s = (s + x.ToString()).Substring(0, 5);
}
料想這代碼該不會被編譯器或JIT優化掉吧？果然，添加後時間對比就比較明顯了：
Normal
Fib(100) = -980107325 (206 ms)
Fib(1000) = 1556111435 (2419 ms)
Fib(10000) = 1242044891 (65435 ms)
/////////////////////////////////////
Recursive
Fib(100) = -980107325 (192 ms)
Fib(1000) = 1556111435 (2735 ms)
Fib(10000) = 1242044891 (103156 ms)
/////////////////////////////////////
TailRecursive
Fib(100) = -980107325 (186 ms)
Fib(1000) = 1556111435 (1889 ms)
Fib(10000) = 1242044891 (18969 ms)
可以看出，在遞歸次數較多的情況下，尾遞歸確實在性能上有較大的優勢。出乎意料的是像Recursive這種簡單的包裝竟然降低了不少性能，不知有哪位大哥可以看看測試代碼，看到底問題出在哪裡？或許哪天我想通了，到時可以再寫篇<續2>呵呵
測試代碼
static void Main(string[] args){ Console.WriteLine("Normal"); int x = 10000; var s = x.ToString(); GC.Collect(); GC.WaitForPendingFinalizers(); Func<int, int, int, int, int> fib1 = null; fib1 = (i, n, a, b) => { x = -x; for (int j = 0; j < Math.Abs(x); j++) { s = (s + x.ToString()).Substring(0, 5); } return (n < 3 ? 1 : (i == n ? a + b : fib1(i + 1, n, b, a + b))); }; Action<int> Fib1 = n => { Console.Write("Fib({0}) = ", n); var sw = System.Diagnostics.Stopwatch.StartNew(); var result = fib1(3, n, 1, 1); sw.Stop(); Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds); }; Fib1(100); Fib1(1000); Fib1(10000); Console.WriteLine("/////////////////////////////////////"); Console.WriteLine("Recursive"); GC.Collect(); GC.WaitForPendingFinalizers(); var fib2 = Recursive<int, int, int, int, int>((self, i, n, a, b) => { x = -x; for (int j = 0; j < Math.Abs(x); j++) { s = (s + x.ToString()).Substring(0, 3); } return (n < 3 ? 1 : (i == n ? a + b : self(i + 1, n, b, a + b))); }); Action<int> Fib2 = n => { Console.Write("Fib({0}) = ", n); var sw = System.Diagnostics.Stopwatch.StartNew(); var result = fib2(3, n, 1, 1); sw.Stop(); Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds); }; Fib2(100); Fib2(1000); Fib2(10000); Console.WriteLine("/////////////////////////////////////"); Console.WriteLine("TailRecursive"); GC.Collect(); GC.WaitForPendingFinalizers(); var fib3 = TailRecursive<int, int, int, int, int>((self, i, n, a, b) => { x = -x; for (int j = 0; j < Math.Abs(x); j++) { s = (s + x.ToString()).Substring(0, 3); } return (n < 3 ? 1 : (i == n ? a + b : self(i + 1, n, b, a + b))); }); Action<int> Fib3 = n => { Console.Write("Fib({0}) = ", n); var sw = System.Diagnostics.Stopwatch.StartNew(); var result = fib3(3, n, 1, 1); sw.Stop(); Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds); }; Fib3(100); Fib3(1000); Fib3(10000);}
