算法:阶乘的五种算法

算法:阶乘的五种算法背景周末温习了一下递归相关的一些概念,本文先给出阶乘的五种算法。第一种实现:递归1privatestaticlongRecursiveFac(longn)2{3if(n==0

大家好,又见面了,我是你们的朋友全栈君。

背景

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

第一种实现:递归

 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 }

备注

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

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155051.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 宽字节注入(一)_低字节在前高字节在后

    宽字节注入(一)_低字节在前高字节在后在PHP中有这样一个函数:magic_quotes_gpc它的作用就是将你输入的特殊字符前面统统加一个\符号如下图前2句话在看下面这条语句之前,我们首先需要知道。\’只能和\’进行闭合下面这个语句,显然不能将1进行闭合。而是将\当成了一个字符串。后面的单引号把后面的给后面的给闭合了。不能闭合,就显然不能进行SQL注入。这就是magic_quotes_gpc函数的作用了。select*fromadminwhereid=’1\’unionselect–+

    2022年10月14日
  • android_使用ViewPager和Fragment实现滑动导航

    ViewPage是android-support-v4.jar包提供的用于页面滑动的库.这里没有将整个实现过程记录,只是把知识点摘出来单独解释.可参照代码自己实现.1.在xml布局文件中添加android.support.v4.view.ViewPager容器及显示导航所用标签android.support.v4.view.PagerTitleStrip,如我添加的xml内容如下

  • srgb的伽马值_srgb模式和标准模式

    srgb的伽马值_srgb模式和标准模式sRGB标准人眼对亮度的感知不是线性的,其对较暗区域的变化更加敏感参见:ComputerColorisBroken基于人眼该特点,sRGB标准要求图像(各通道为8bits,最多存储256个亮度值)使用编码伽马,把更多地空间用来存储更多暗部区域,来最大化地利用表示亮度的数据位或带宽伽马校正(Gammacorrection)在早期,阴极射线管(CRT)显示器是唯一的电子显示设备,但它的输入电压和显示出来的亮度关系不是线性的,而是一个类似幂律(pow-law)曲线的关系,…

  • SVN——SVN项目迁移到GIT

    svn有很多优点,但是git的出现对svn的冲击的确很大,现在很多公司项目的都迁移的git上了,下面是我自己在做svn迁移项目到git上面时候整理的一些资料。暂时就些整理这些,具体的操作如果有看不懂的,可以和我联系!右侧的qq号,欢迎一起探讨。 相关操作: 1:命令行执行##clone svn -> git 地址支持协议 : svn://, http://, https://. 注意这个 UR

  • nginx reload不生效_nginx权重配置

    nginx reload不生效_nginx权重配置解释/usr/local/nginx/sbin/nginx-sreload 用过多次这条命令,一直以为是重启Nginx,今天有幸看了下Nginx官方文档介绍这条命令 Nginx服务不会终止,主进程检查配置,应用配置的过程。主进程会启动一个新的工作进程处理新来的请求。主进程发送消息给老的工作进程,通知老的进程不在接受请求,处理完现有的请求后退出(优雅退出) …

    2022年10月31日
  • android之OnTouchListener只能监听到ACTION_DOWN—–onTouchListener的返回值问题「建议收藏」

    做这样一个效果,界面上显示一个紫色方块,任意拖动方块到指定位置都可以,结果方块不动,打印log只有ACTION_DOWN有反应,MOVE和UP都监听不到,很是奇怪,先把整段代码都贴下面了package jason.com.security.ui;import jason.com.security.R;import android.app.Activity;import

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号