大家好，又见面了，我是你们的朋友全栈君。
背景
周末温习了一下递归相关的一些概念，本文先给出阶乘的五种算法。
第一种实现：递归
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 }
备注
这里比较有意思的实现是：尾递归和基于堆中的栈的递归，本文先不详细介绍了，后面再细说，有兴趣的朋友先看如下资源：
- 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。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155051.html原文链接：https://javaforall.net
