题
我想看看您可以为阶乘子例程或程序想出所有不同的方法。希望任何人都可以来这里看看他们是否想学习一门新语言。
想法:
- 程序
- 功能性
- 面向对象
- 1个衬垫
- 混淆
- 奇怪的
- 错误代码
- 多语言
基本上我想看一个示例,说明编写算法的不同方式,以及它们在不同语言中的外观。
请将每个条目限制为一个示例。如果您想强调一种特定的风格、语言,或者只是一个适合在一篇文章中出现的深思熟虑的想法,我将允许您为每个答案提供多个示例。
唯一真正的要求是它必须在所表示的所有语言中找到给定参数的阶乘。
要有创意!
推荐指南:
# Language Name: Optional Style type - Optional bullet points Code Goes Here Other informational text goes here
我偶尔会去编辑任何格式不正确的答案。
解决方案
多语言:5 种语言,全部使用 bignum
因此,我编写了一种多语言程序,可以使用我经常使用的三种语言,以及我对这个问题的其他答案中的一种语言和我今天刚刚学到的一种语言。它是一个独立的程序,它读取包含非负整数的单行并打印包含其阶乘的单行。Bignum 用于所有语言,因此最大可计算阶乘仅取决于计算机的资源。
- 珀尔: :使用内置的bignum包。运行与
perl FILENAME
. - 哈斯克尔: :使用内置的 bignum。运行与
runhugs FILENAME
或您最喜欢的编译器的等效版本。 - C++: :需要 GMP 来支持 bignum。要使用 g++ 编译,请使用
g++ -lgmpxx -lgmp -x c++ FILENAME
链接到正确的库。编译完成后,运行./a.out
. 。或者使用您最喜欢的编译器的等效版本。 - 脑残*ck: :我写了一些bignum支持 这个帖子. 。使用 Muller 的经典分布, ,编译为
bf < FILENAME > EXECUTABLE
. 。使输出可执行并运行它。或者使用您最喜欢的发行版。 - 空白: :使用内置的 bignum 支持。运行与
wspace FILENAME
.
编辑: 添加空白作为第五种语言。顺便说一下,做 不是 将代码包装为 <code>
标签;它打破了空白。此外,固定宽度的代码看起来更好。
char //# b=0+0{- |0*/; #>>>>,----------[>>>>,-------- #define a/*#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<< #Perl ><><><> <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<-> #C++ --><><> <><><>< > < > < +<[>>>>+<<<-<[-]]>[-] #Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>] #Whitespace >>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<< #brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/ exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5. #include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>> #define eval int main()//>+<<<-]>>>[<<<+>>+>-> #include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>> #define print std::cout << // > <+<-]>[<<+>+>-]<<[>>> #define z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++ #define c/*++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<<*/ #define abs int $n //>< <]<[>>+<<<<[-]>>[<<+>>-]]>>]< #define uc mpz_class fact(int $n){/*<<<[<<<<]<<<[<< use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-] z{$_[0+0]=readline(*STDIN);}sub fact{my($n)=shift;#>> #[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+*/ uc;if($n==0){return 1;}return $n*fact($n-1); }//;# eval{abs;z($n);print fact($n);print("\n")/*2;};#-]<-> '+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++ -}-- <[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++ fact 0 = 1 -- ><><><>< > <><>< ]+<[>-<[-]]>]<<[<<+ + fact n=n*fact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-} main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+ {-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-] <--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x*/;}
其他提示
哈哈代码:
抱歉我无法抗拒xD
HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
UP VAR!!1
TIEMZD INT!![CHEEZBURGER]
UP FACTORIALNUM!!1
IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE
C++:模板元编程
使用经典的枚举技巧。
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
用法。
const unsigned int x = factorial<4>::result;
阶乘完全在编译时根据模板参数 n 计算。因此,一旦编译器完成其工作,factorial<4>::result 就是一个常量。
空白
. . . . . . . . . . . . . . . . . . . . . . . . . .
很难让它在这里正确显示,但现在我尝试从预览中复制它并且它有效。您需要输入号码并按 Enter 键。
C# 查找:
其实没什么可计算的,查一下就知道了。要扩展它,请在表中添加另外 8 个数字,64 位整数已达到极限。除此之外,还需要一个 BigNum 类。
public static int Factorial(int f)
{
if (f<0 || f>12)
{
throw new ArgumentException("Out of range for integer factorial");
}
int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
39916800,479001600};
return fact[f];
}
懒惰的 K
你的纯函数式编程噩梦成真了!
唯一的 深奥的图灵完备编程语言 具有:
这是阶乘代码及其所有括号的优点:
K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
(S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)
特征:
- 没有减法或条件
- 打印所有阶乘(如果您等待足够长的时间)
- 使用第二层 Church 数字将第 N 个阶乘转换为 N!星号后跟换行符
- 使用 Y组合器 用于递归
如果您有兴趣尝试理解它,这里是通过 Lazier 编译器运行的方案源代码:
(lazy-def '(fac input)
'((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
(* a n)))) 1 1))
(Y、cons、1、10、42、1+ 和 * 的合适定义)。
编辑:
十进制惰性 K 阶乘
(10KB 的乱码 不然我就粘贴它)。例如,在 Unix 提示符下:
$ echo "4" | ./lazy facdec.lazy 24 $ echo "5" | ./lazy facdec.lazy 120
对于上面的数字(例如 5)来说相当慢。
代码有点臃肿,因为我们必须包含 我们自己所有原语的库代码 (代码写在 朦胧, ,一个用 Haskell 编写的 lambda 演算解释器和 LC-to-Lazy K 编译器)。
XSLT 1.0
输入文件, 阶乘.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
XSLT 文件, 阶乘.xsl:
<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
<xsl:output method="text"/>
<!-- 0! = 1 -->
<xsl:template match="text()[. = 0]">
1
</xsl:template>
<!-- n! = (n-1)! * n-->
<xsl:template match="text()[. > 0]">
<xsl:variable name="x">
<xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
</xsl:variable>
<xsl:value-of select="$x * ."/>
</xsl:template>
<!-- Calculate n! -->
<xsl:template match="/n">
<xsl:apply-templates select="text()"/>
</xsl:template>
</xsl:stylesheet>
将两个文件保存在同一目录中并打开 阶乘.xml 在IE中。
Python:功能性、单行
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
笔记:
- 它支持大整数。例子:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- 它不适用于 n < 0.
APL (奇怪/单行):
×/⍳X
- ⍳X 将 X 扩展为整数数组 1..X
- ×/ 乘以数组中的每个元素
或者使用内置运算符:
!X
来源: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
x86-64 组件:程序
您可以从 C 调用它(仅在 Linux amd64 上使用 GCC 进行测试)。程序集是用 nasm 组装的。
section .text
global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
; extern unsigned long long factorial(unsigned long long n);
factorial:
enter 0,0
; n is placed in rdi by caller
mov rax, 1 ; factorial = 1
mov rcx, 2 ; i = 2
loopstart:
cmp rcx, rdi
ja loopend
mul rcx ; factorial *= i
inc rcx
jmp loopstart
loopend:
leave
ret
Inform 7 中的递归
(它让你想起 COBOL,因为它用于编写文本冒险;比例字体是故意的):
要确定哪个数字是 (n - 数字) 的阶乘:
如果 n 为零,则决定为 1;
否则决定 (n 减一) 乘以 n 的阶乘。
如果您想在游戏中实际调用此函数(“短语”),您需要定义一个动作和语法规则:
“阶乘游戏”[这必须是源代码的第一行]
有一个房间。【至少要有一个!】
阶乘是应用于数字的操作。
将“阶乘[数字]”理解为阶乘。
进行阶乘:
令 n 为所理解数字的阶乘;
说“这是[n]”。
C#:LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
埃尔兰:尾递归
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
哈斯克尔:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
脑残*ck
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
由迈克尔·雷岑斯坦撰写。
基本的:老套
10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50 ANS = ANS * I
60 NEXT I
70 PRINT ANS
批次(新台币):
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
用法:C:>阶乘.bat 15
F#:功能性
直接说:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
变得花哨:
let fact x = [1 .. x] |> List.fold_left ( * ) 1
递归序言
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
尾递归 Prolog
fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).
红宝石递归
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
用法:
factorial[5]
=> 120
方案
这是一个简单的递归定义:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
在Scheme中,尾递归函数使用恒定的堆栈空间。这是尾递归的阶乘版本:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
奇怪的例子?使用伽玛函数怎么样!自从, Gamma n = (n-1)!
.
奥卡姆:使用伽玛
let rec gamma z =
let pi = 4.0 *. atan 1.0 in
if z < 0.5 then
pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
else
let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
771.32342877765313; -176.61502916214059; 12.507343278686905;
-0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
|]
in
let z = z -. 1.0 in
let results = Array.fold_right
(fun x y -> x +. y)
(Array.mapi
(fun i x -> if i = 0 then x else x /. (z+.(float i)))
consts
)
0.0
in
let x = z +. (float (Array.length consts)) -. 1.5 in
let final = (sqrt (2.0*.pi)) *.
(x ** (z+.0.5)) *.
(exp (-.x)) *. result
in
final
let factorial_gamma n = int_of_float (gamma (float (n+1)))
新生 Haskell 程序员
fac n = if n == 0
then 1
else n * fac (n-1)
大二学生Haskell程序员,在麻省理工学院(新生学习计划)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Junior Haskell程序员(开始的Peano播放器)
fac 0 = 1
fac (n+1) = (n+1) * fac n
另一个初级Haskell程序员(请阅读N+K模式是“ Haskell的一个令人恶心的部分” [1],并加入了“ Ban N+K模式” -Movement [2])
fac 0 = 1
fac n = n * fac (n-1)
高级Haskell程序员(投票赞成尼克松·布坎南灌木丛 - “靠在右边”)
fac n = foldr (*) 1 [1..n]
另一位高级Haskell程序员(投票赞成McGovern Biafra Nader - “左左”)
fac n = foldl (*) 1 [1..n]
还有另一位高级Haskell程序员(向右倾斜,他又回来了!)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
纪念Haskell程序员(每天服用Ginkgo Biloba)
facs = scanl (*) 1 [1..]
fac n = facs !! n
毫无意义(ahem)“无点” Haskell程序员(牛津大学学习)
fac = foldr (*) 1 . enumFromTo 1
迭代Haskell程序员(前Pascal程序员)
fac n = result (for init next done)
where init = (0,1)
next (i,m) = (i+1, m * (i+1))
done (i,_) = i==n
result (_,m) = m
for i n d = until d n i
迭代单线Haskell程序员(前APL和C编程器)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
累积Haskell程序员(建立高潮)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
持续通过的Haskell程序员(早年饲养兔子,然后搬到新泽西州)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
童子军Haskell程序员(喜欢打结;他总是“崇敬”,他属于最不定点的教会[8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
组合性Haskell程序员(如果不是混淆,则避开变量;所有这些柯里化只是一个阶段,尽管它很少阻碍)
s f g x = f x (g x)
k x y = x
b f g x = f (g x)
c f g x = f x g
y f = f (y f)
cond p f g x = if p x then f x else g x
fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))
列表编码HASKELL程序员(偏爱一单元计数)
arb = () -- "undefined" is also a good RHS, as is "arb" :)
listenc n = replicate n arb
listprj f = length . f . listenc
listprod xs ys = [ i (x,y) | x<-xs, y<-ys ]
where i _ = arb
facl [] = listenc 1
facl n@(_:pred) = listprod n (facl pred)
fac = listprj facl
解释性的Haskell程序员(从未遇到他不喜欢的语言)
-- a dynamically-typed term language
data Term = Occ Var
| Use Prim
| Lit Integer
| App Term Term
| Abs Var Term
| Rec Var Term
type Var = String
type Prim = String
-- a domain of values, including functions
data Value = Num Integer
| Bool Bool
| Fun (Value -> Value)
instance Show Value where
show (Num n) = show n
show (Bool b) = show b
show (Fun _) = ""
prjFun (Fun f) = f
prjFun _ = error "bad function value"
prjNum (Num n) = n
prjNum _ = error "bad numeric value"
prjBool (Bool b) = b
prjBool _ = error "bad boolean value"
binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))
-- environments mapping variables to values
type Env = [(Var, Value)]
getval x env = case lookup x env of
Just v -> v
Nothing -> error ("no value for " ++ x)
-- an environment-based evaluation function
eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m
-- a (fixed) "environment" of language primitives
times = binOp Num (*)
minus = binOp Num (-)
equal = binOp Bool (==)
cond = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))
prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]
-- a term representing factorial and a "wrapper" for evaluation
facTerm = Rec "f" (Abs "n"
(App (App (App (Use "if")
(App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
(App (App (Use "*") (Occ "n"))
(App (Occ "f")
(App (App (Use "-") (Occ "n")) (Lit 1))))))
fac n = prjNum (eval [] (App facTerm (Lit n)))
Static Haskell程序员(他在课堂上做到了,他有那个Fundep Jones!继 Thomas Hallgren 的“函数依赖的乐趣”之后 [7])
-- static Peano constructors and numerals
data Zero
data Succ n
type One = Succ Zero
type Two = Succ One
type Three = Succ Two
type Four = Succ Three
-- dynamic representatives for static Peanos
zero = undefined :: Zero
one = undefined :: One
two = undefined :: Two
three = undefined :: Three
four = undefined :: Four
-- addition, a la Prolog
class Add a b c | a b -> c where
add :: a -> b -> c
instance Add Zero b b
instance Add a b c => Add (Succ a) b (Succ c)
-- multiplication, a la Prolog
class Mul a b c | a b -> c where
mul :: a -> b -> c
instance Mul Zero b Zero
instance (Mul a b c, Add b c d) => Mul (Succ a) b d
-- factorial, a la Prolog
class Fac a b | a -> b where
fac :: a -> b
instance Fac Zero One
instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m
-- try, for "instance" (sorry):
--
-- :t fac four
初学者Haskell程序员(研究生教育倾向于将一个人摆脱对基于硬件整数的效率的小问题)
-- the natural numbers, a la Peano
data Nat = Zero | Succ Nat
-- iteration and some applications
iter z s Zero = z
iter z s (Succ n) = s (iter z s n)
plus n = iter n Succ
mult n = iter Zero (plus n)
-- primitive recursion
primrec z s Zero = z
primrec z s (Succ n) = s n (primrec z s n)
-- two versions of factorial
fac = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))
fac' = primrec one (mult . Succ)
-- for convenience and testing (try e.g. "fac five")
int = iter 0 (1+)
instance Show Nat where
show = show . int
(zero : one : two : three : four : five : _) = iterate Succ Zero
折纸家Haskell程序员(总是从“基本鸟折”开始)
-- (curried, list) fold and an application
fold c n [] = n
fold c n (x:xs) = c x (fold c n xs)
prod = fold (*) 1
-- (curried, boolean-based, list) unfold and an application
unfold p f g x =
if p x
then []
else f x : unfold p f g (g x)
downfrom = unfold (==0) id pred
-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)
refold c n p f g = fold c n . unfold p f g
refold' c n p f g x =
if p x
then n
else c (f x) (refold' c n p f g (g x))
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = refold (*) 1 (==0) id pred
fac'' = refold' (*) 1 (==0) id pred
卡特西亚的哈斯克尔程序员(喜欢希腊食品,避免了辛辣的印度东西;灵感来自 Lex Augusteijn 的“Sorting Morphisms”[3])
-- (product-based, list) catamorphisms and an application
cata (n,c) [] = n
cata (n,c) (x:xs) = c (x, cata (n,c) xs)
mult = uncurry (*)
prod = cata (1, mult)
-- (co-product-based, list) anamorphisms and an application
ana f = either (const []) (cons . pair (id, ana f)) . f
cons = uncurry (:)
downfrom = ana uncount
uncount 0 = Left ()
uncount n = Right (n, n-1)
-- two variations on list hylomorphisms
hylo f g = cata g . ana f
hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f
pair (f,g) (x,y) = (f x, g y)
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = hylo uncount (1, mult)
fac'' = hylo' uncount (1, mult)
博士Haskell程序员(吃了很多香蕉,他的眼睛被烦扰了,现在他需要新的镜头!)
-- explicit type recursion based on functors
newtype Mu f = Mu (f (Mu f)) deriving Show
in x = Mu x
out (Mu x) = x
-- cata- and ana-morphisms, now for *arbitrary* (regular) base functors
cata phi = phi . fmap (cata phi) . out
ana psi = in . fmap (ana psi) . psi
-- base functor and data type for natural numbers,
-- using a curried elimination operator
data N b = Zero | Succ b deriving Show
instance Functor N where
fmap f = nelim Zero (Succ . f)
nelim z s Zero = z
nelim z s (Succ n) = s n
type Nat = Mu N
-- conversion to internal numbers, conveniences and applications
int = cata (nelim 0 (1+))
instance Show Nat where
show = show . int
zero = in Zero
suck = in . Succ -- pardon my "French" (Prelude conflict)
plus n = cata (nelim n suck )
mult n = cata (nelim zero (plus n))
-- base functor and data type for lists
data L a b = Nil | Cons a b deriving Show
instance Functor (L a) where
fmap f = lelim Nil (\a b -> Cons a (f b))
lelim n c Nil = n
lelim n c (Cons a b) = c a b
type List a = Mu (L a)
-- conversion to internal lists, conveniences and applications
list = cata (lelim [] (:))
instance Show a => Show (List a) where
show = show . list
prod = cata (lelim (suck zero) mult)
upto = ana (nelim Nil (diag (Cons . suck)) . out)
diag f x = f x x
fac = prod . upto
DOC HASKELL程序员(来自Uastalu,Vene和Pardo的“来自ComOnads的递归计划” [4])
-- explicit type recursion with functors and catamorphisms
newtype Mu f = In (f (Mu f))
unIn (In x) = x
cata phi = phi . fmap (cata phi) . unIn
-- base functor and data type for natural numbers,
-- using locally-defined "eliminators"
data N c = Z | S c
instance Functor N where
fmap g Z = Z
fmap g (S x) = S (g x)
type Nat = Mu N
zero = In Z
suck n = In (S n)
add m = cata phi where
phi Z = m
phi (S f) = suck f
mult m = cata phi where
phi Z = zero
phi (S f) = add m f
-- explicit products and their functorial action
data Prod e c = Pair c e
outl (Pair x y) = x
outr (Pair x y) = y
fork f g x = Pair (f x) (g x)
instance Functor (Prod e) where
fmap g = fork (g . outl) outr
-- comonads, the categorical "opposite" of monads
class Functor n => Comonad n where
extr :: n a -> a
dupl :: n a -> n (n a)
instance Comonad (Prod e) where
extr = outl
dupl = fork id outr
-- generalized catamorphisms, zygomorphisms and paramorphisms
gcata :: (Functor f, Comonad n) =>
(forall a. f (n a) -> n (f a))
-> (f (n c) -> c) -> Mu f -> c
gcata dist phi = extr . cata (fmap phi . dist . fmap dupl)
zygo chi = gcata (fork (fmap outl) (chi . fmap outr))
para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c
para = zygo In
-- factorial, the *hard* way!
fac = para phi where
phi Z = suck zero
phi (S (Pair f n)) = mult f (suck n)
-- for convenience and testing
int = cata phi where
phi Z = 0
phi (S f) = 1 + f
instance Show (Mu N) where
show = show . int
终身教授(对新生的Haskell教学)
fac n = product [1..n]
D 模板:功能性
template factorial(int n : 1)
{
const factorial = 1;
}
template factorial(int n)
{
const factorial =
n * factorial!(n-1);
}
或者
template factorial(int n)
{
static if(n == 1)
const factorial = 1;
else
const factorial =
n * factorial!(n-1);
}
像这样使用:
factorial!(5)
Java 1.6:递归、记忆(用于后续调用)
private static Map<BigInteger, BigInteger> _results = new HashMap()
public static BigInteger factorial(BigInteger n){
if (0 >= n.compareTo(BigInteger.ONE))
return BigInteger.ONE.max(n);
if (_results.containsKey(n))
return _results.get(n);
BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
_results.put(n, result);
return result;
}
电源外壳
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
这是一行:
$n..1 | % {$result = 1}{$result *= $_}{$result}
重击:递归
在 bash 和递归中,但具有额外的优点,它处理新进程中的每次迭代。它在溢出之前可以计算的最大值是 !20,但是如果您不关心答案并希望系统崩溃,您仍然可以运行它来计算大数字;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));