算法:阶乘的五种算法

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


相关推荐

  • java 舆情分析_基于Java实现网络舆情分析系统研究与实现.doc[通俗易懂]

    java 舆情分析_基于Java实现网络舆情分析系统研究与实现.doc[通俗易懂]基于Java实现网络舆情分析系统研究与实现基于Java实现网络舆情分析系统研究与实现摘要:通过对各大门户网站、论坛和贴吧的留言和评论的爬取,录入后台数据库。用户可根据主题、内容进行搜索查看。通过利用中科院分词算法进行实现对爬去下来的内容进行分词处理,分词处理后的结果利用自行研究出来的基于权值算法实现的中文情感分析进行评论的倾向性分析,通过对句子结构和主张词以及情感副词的判断来对评论的情感倾向性做出…

  • 高曼数位板触控笔无反应问题

    高曼数位板触控笔无反应问题

  • android共享文件夹_安卓多用户共享文件

    android共享文件夹_安卓多用户共享文件AndroidN之前的Uri常规Uri有两种:媒体文件的Uri是content://,表示这是一个数据库数据。去数据库查询正常返回。其他的文件Uri是file://,表示这个是一个文件。这个uri是通过Uri.fromFile(Filefile)方法生成。AndroidN之前,这些uri可以传递到其他应用。AndroidN中共享文件Android

  • 已知圆心及半径,通过MATLAB画圆「建议收藏」

    已知圆心及半径,通过MATLAB画圆「建议收藏」已知圆心及半径,使用MATLAB画圆文章目录已知圆心及半径,使用MATLAB画圆一、原理简介二、转换过程三、结果展示一、原理简介条件中已知圆的半径可以等价于极坐标系中的ρ,所以能根据已知的半径转换为直角坐标系中点的坐标来画圆。转换的原理是使用极坐标与直角坐标之间的转换公式来实现,公式如下:x=ρcosθy=ρsinθ二、转换过程主要分一下几步完成1.设置圆的一周由多少个点组成;2.设置圆周上点与点之间的间隔角度;3.设置圆心的坐标;4.读取半径值;5.求取X、Y轴坐标;6.画

  • 使用adb logcat命令显示Android设备上的Log日志

    使用adb logcat命令显示Android设备上的Log日志使用adblogcat命令显示Android设备上的Log日志有时候我们在手机程序上的日志要在其他地方调试,然后要看里面的Log日志。本文教大家如何在不需要studio就可以查看手机程序中的Log日志。实现这个功能的前提是使用adb命令,所以必须要有手机和电脑,还有安装adb,adb程序是很小的几M就可以。一.在cmd窗口查看手机的Log日志在确定连上手机后(adbdevi…

  • 文件io之——open/close

    文件io之——open/close

发表回复

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

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