|
背景
周末温习了一下递归相关的一些概念，本文先给出阶乘的五种算法。
第一种实现：递归
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 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。
|