背景

周末溫習了一下遞歸相關的一些概念,本文先給出階乘的五種算法。

第一種實現:遞歸

 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 StackFrame20             {21                 N = n,22                 CodeAddress = CodeAddress.Start23             });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                         else40                         {41                             current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;42                             stack.Push(new StackFrame43                             {44                                 N = current.N - 1,45                                 CodeAddress = CodeAddress.Start46                             });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         }

備注

這里比較有意思的實現是:尾遞歸和基于堆中的棧的遞歸,本文先不詳細介紹了,后面再細說,有興趣的朋友先看如下資源:

• Replacing Recursion With a Stack。
• How to replace recursive functions using stack and while-loop to avoid the stack-overflow。
• HOW TO CONVERT A RECURSIVE ALGORITHM TO A NON-RECURSIVE ONE。
• replace Recursion with Iteration。
• Provide an explanation of recursion, including an example。
• Tail Recursion。
• Understanding Tail Recursion。

155051.html