2025年3月17日 星期一 甲辰(龙)年 月十六 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

算法:阶乘的五种算法

时间:11-22来源:作者:点击数:60
背景

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

第一种实现:递归
  • 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;
  • }
备注

这里比较有意思的实现是:尾递归和基于堆中的栈的递归,本文先不详细介绍了,后面再细说,有兴趣的朋友先看如下资源:

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门