背景

周末温习了一下递归相关的一些概念，本文先给出阶乘的五种算法。

第一种实现：递归

 1         private static long RecursiveFac(long n)
 2         {
 3             if (n == 0)
 4             {
 5                 return 1;
 6             }
 7             else
 8             {
 9                 return n * RecursiveFac(n - 1);
10             }
11         }

第二种实现：递推

 1         private static long Fac(long n)
 2         {
 3             var result = 1;
 4 
 5             for (var i = 1; i <= n; i++)
 6             {
 7                 result = result * i;
 8             }
 9 
10             return result;
11         }

第三种实现：尾递归

1         private static int TailRecursiveFac(int n, int accumulator)
2         {
3             if (n == 0)
4             {
5                 return accumulator;
6             }
7 
8             return Fac(n - 1, n * accumulator);
9         }

第四种实现：消除尾递归

 1         private static int Fac(int n, int accumulator)
 2         {
 3             while (true)
 4             {
 5                 var tempN = n;
 6                 var tempAccumulator = accumulator;
 7 
 8                 if (tempN == 0)
 9                 {
10                     return tempAccumulator;
11                 }
12 
13                 n = tempN - 1;
14                 accumulator = tempN * tempAccumulator;
15             }
16         }

第五种实现：堆栈（堆中分配的栈）替换函数栈

 1         private enum CodeAddress
 2         {
 3             Start,
 4             AfterFirstRecursiveCall
 5         }
 6 
 7         private class StackFrame
 8         {
 9             public long N { get; set; }
10 
11             public long FirstRecursiveCallResult { get; set; }
12 
13             public CodeAddress CodeAddress { get; set; }
14         }
15 
16         private static long StackFac(long n)
17         {
18             var stack = new Stack<StackFrame>();
19             stack.Push(new StackFrame
20             {
21                 N = n,
22                 CodeAddress = CodeAddress.Start
23             });
24 
25             long result = 0;
26 
27             while (stack.Count > 0)
28             {
29                 var current = stack.Peek();
30 
31                 switch (current.CodeAddress)
32                 {
33                     case CodeAddress.Start:
34                         if (current.N == 0)
35                         {
36                             result = 1;
37                             stack.Pop();
38                         }
39                         else
40                         {
41                             current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;
42                             stack.Push(new StackFrame
43                             {
44                                 N = current.N - 1,
45                                 CodeAddress = CodeAddress.Start
46                             });
47                         }
48                         break;
49                     case CodeAddress.AfterFirstRecursiveCall:
50                         current.FirstRecursiveCallResult = result;
51 
52                         result = current.N * current.FirstRecursiveCallResult;
53                         stack.Pop();
54                         break;
55                 }
56             }
57 
58             return result;
59         }