周末温习了一下递归相关的一些概念,本文先给出阶乘的五种算法。
- private static long RecursiveFac(long n)
- {
- if (n == 0)
- {
- return 1;
- }
- else
- {
- return n * RecursiveFac(n - 1);
- }
- }
- private static long Fac(long n)
- {
- var result = 1;
-
- for (var i = 1; i <= n; i++)
- {
- result = result * i;
- }
-
- return result;
- }
- private static int TailRecursiveFac(int n, int accumulator)
- {
- if (n == 0)
- {
- return accumulator;
- }
-
- return Fac(n - 1, n * accumulator);
- }
- private static int Fac(int n, int accumulator)
- {
- while (true)
- {
- var tempN = n;
- var tempAccumulator = accumulator;
-
- if (tempN == 0)
- {
- return tempAccumulator;
- }
-
- n = tempN - 1;
- accumulator = tempN * tempAccumulator;
- }
- }
- private enum CodeAddress
- {
- Start,
- AfterFirstRecursiveCall
- }
-
- private class StackFrame
- {
- public long N { get; set; }
-
- public long FirstRecursiveCallResult { get; set; }
-
- public CodeAddress CodeAddress { get; set; }
- }
-
- private static long StackFac(long n)
- {
- var stack = new Stack<StackFrame>();
- stack.Push(new StackFrame
- {
- N = n,
- CodeAddress = CodeAddress.Start
- });
-
- long result = 0;
-
- while (stack.Count > 0)
- {
- var current = stack.Peek();
-
- switch (current.CodeAddress)
- {
- case CodeAddress.Start:
- if (current.N == 0)
- {
- result = 1;
- stack.Pop();
- }
- else
- {
- current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;
- stack.Push(new StackFrame
- {
- N = current.N - 1,
- CodeAddress = CodeAddress.Start
- });
- }
- break;
- case CodeAddress.AfterFirstRecursiveCall:
- current.FirstRecursiveCallResult = result;
-
- result = current.N * current.FirstRecursiveCallResult;
- stack.Pop();
- break;
- }
- }
-
- return result;
- }
这里比较有意思的实现是:尾递归和基于堆中的栈的递归,本文先不详细介绍了,后面再细说,有兴趣的朋友先看如下资源: