Algoritmos factoriales en diferentes idiomas

https://stackoverflow.com/questions/23930

09-06-2019
|

Pregunta

Quiero ver todas las diferentes formas que se te ocurren para una subrutina o programa factorial.La esperanza es que cualquiera pueda venir aquí y ver si quiere aprender un nuevo idioma.

Ideas:

Procesal
Funcional
Orientado a objetos
Una sola línea
Ofuscado
Bicho raro
Código incorrecto
Polígloto

Básicamente, quiero ver un ejemplo de diferentes formas de escribir un algoritmo y cómo se verían en diferentes idiomas.

Limítelo a un ejemplo por entrada.Te permitiré tener más de un ejemplo por respuesta, si estás tratando de resaltar un estilo, lenguaje específico o simplemente una idea bien pensada que se presta a estar en una publicación.

El único requisito real es encontrar el factorial de un argumento determinado, en todos los idiomas representados.

¡Ser creativo!

Pauta recomendada:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

De vez en cuando editaré cualquier respuesta que no tenga un formato decente.

Solución

Polígloto:5 idiomas, todos usando bignums

Entonces, escribí un políglota que funciona en los tres idiomas en los que escribo a menudo, así como uno de mi otra respuesta a esta pregunta y uno que acabo de aprender hoy.Es un programa independiente, que lee una sola línea que contiene un número entero no negativo e imprime una sola línea que contiene su factorial.Bignums se utiliza en todos los idiomas, por lo que el factorial computable máximo depende únicamente de los recursos de su computadora.

perla:utiliza el paquete bignum incorporado.Corre con perl FILENAME.
Haskell:utiliza bignums incorporados.Corre con runhugs FILENAME o el equivalente de su compilador favorito.
C++:requiere GMP para el soporte de bignum.Para compilar con g++, use g++ -lgmpxx -lgmp -x c++ FILENAME para vincular con las bibliotecas adecuadas.Después de compilar, ejecute ./a.out.O utilice el equivalente de su compilador favorito.
mierda cerebral:Escribí algo de soporte bignum en esta publicación.Usando Distribución clásica de Muller, compilar con bf < FILENAME > EXECUTABLE.Haga que la salida sea ejecutable y ejecútela.O utiliza tu distribución favorita.
Espacio en blanco:utiliza soporte bignum incorporado.Corre con wspace FILENAME.

Editar: Añadió espacios en blanco como quinto idioma.Por cierto, hazlo no envuelve el código con <code> etiquetas;rompe el espacio en blanco.Además, el código se ve mucho mejor en ancho fijo.

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*/;}

Otros consejos

código jajaja:

Lo siento, no pude resistirme 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

Este es uno de los algoritmos más rápidos, hasta 170!.Él falla inexplicablemente más allá de 170!, y es relativamente lento para factoriales pequeños, pero para factoriales entre 80 y 170 Es increíblemente rápido en comparación con muchos algoritmos.

curl http://www.google.com/search?q=170!

También hay una interfaz en línea, ¡Pruébalo ahora!

Avíseme si encuentra un error o una implementación más rápida para factoriales grandes.

EDITAR:

Este algoritmo es un poco más lento, pero da resultados superiores a 170:

curl http://www58.wolframalpha.com/input/?i=171!

También los simplifica en varias otras representaciones.

C++:Metaprogramación de plantillas

Utiliza el truco de enumeración clásico.

template<unsigned int n>
struct factorial {
    enum { result = n * factorial<n - 1>::result };
};

template<>
struct factorial<0> {
    enum { result = 1 };
};

Uso.

const unsigned int x = factorial<4>::result;

El factorial se calcula completamente en tiempo de compilación según el parámetro de plantilla n.Por lo tanto, factorial<4>::result es una constante una vez que el compilador ha hecho su trabajo.

Espacio en blanco

   	.
 .
 	.
		.
  	.
   	.
			 .
 .
	 	 .
	  .
   	.
 .
  .
 			 .
		  			 .
 .
	.
.
  	 .
 .
.
	.
 	.
.
.
.

Fue difícil mostrarlo aquí correctamente, pero ahora intenté copiarlo desde la vista previa y funciona.Debe ingresar el número y presionar Enter.

Encuentro las siguientes implementaciones simplemente divertidas:

La evolución de un programador Haskell

Evolución de un programador Python

¡Disfrutar!

Búsqueda de C#:

Realmente no hay nada que calcular, solo búscalo.Para ampliarlo, agregue otros 8 números a la tabla y los enteros de 64 bits estarán en su límite.Más allá de eso, se requiere una clase 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];
}

Perezoso k

¡Tus pesadillas de programación puramente funcional se hacen realidad!

El único Lenguaje de programación esotérico Turing completo que tiene:

Una base, un núcleo y bibliotecas puramente funcionales; de hecho, aquí está la API completa: ESQUÍ
No lambdas ¡incluso!
No números o listas necesarias o permitidas
No hay recursividad explícita pero todavía, permite la recursividad
Un simple corriente perezosa infinitaMecanismo de E/S basado en

Aquí está el código Factorial en todo su esplendor entre paréntesis:

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)

Características:

Sin restas ni condicionales
Imprime todos los factoriales (si esperas lo suficiente)
Utiliza una segunda capa de números de Church para convertir el enésimo factorial en N.asteriscos seguidos de una nueva línea
Utiliza el combinador Y para recursividad

En caso de que esté interesado en intentar entenderlo, aquí está el código fuente de Scheme para ejecutarlo a través del compilador 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))

(para definiciones adecuadas de Y, contras, 1, 10, 42, 1+ y *).

EDITAR:

Factorial perezoso K en decimal

(10 KB de galimatías o sino lo pegaría).Por ejemplo, en el indicador de Unix:

    $ echo "4" | ./lazy facdec.lazy
    24
    $ echo "5" | ./lazy facdec.lazy
    120

Bastante lento para números superiores, digamos, 5.

El código está algo inflado porque tenemos que incluir código de biblioteca para todas nuestras propias primitivas (código escrito en Brumoso, un intérprete de cálculo lambda y compilador LC-to-Lazy K escrito en Haskell).

XSLT 1.0

El archivo de entrada, factorial.xml:

<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
  20
</n>

El archivo XSLT, factorial.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>

Guarde ambos archivos en el mismo directorio y ábralos. factorial.xml en IE.

Pitón:Funcional, de una sola línea

factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)

NOTA:

Admite números enteros grandes.Ejemplo:

print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000

No funciona para norte < 0.

APL (bicho raro/de una sola línea):

×/⍳X

⍳X expande X en una matriz de números enteros 1..X
×/ multiplica cada elemento de la matriz

O con el operador incorporado:

!X

Fuente: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

Perl6

sub factorial ($n) { [*] 1..$n }

Apenas conozco Perl6.Pero supongo que esto [*] El operador es el mismo que el de Haskell. product.

Este código se ejecuta en pugs, y tal vez Loro (No lo comprobé).

Editar

Este código también funciona.

sub postfix:<!> ($n) { [*] 1..$n }

# This function(?) call like below ... It looks like mathematical notation.
say 10!;

Asamblea x86-64:Procesal

Puede llamar a esto desde C (solo probado con GCC en Linux AMD64).La asamblea se montó con 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

Recursivamente en Inform 7

(te recuerda a COBOL porque es para escribir aventuras de texto;la fuente proporcional es deliberada):

Para decidir qué número es el factorial de (n - un número):
si n es cero, decídase por uno;
en caso contrario, decida el factorial de (n menos uno) multiplicado por n.

Si realmente quieres llamar a esta función ("frase") desde un juego, necesitas definir una acción y una regla gramatical:

"El juego factorial" [esta debe ser la primera línea de la fuente]

Hay una habitación.[¡Tiene que haber al menos uno!]

Factorizar es una acción que se aplica a un número.

Entiende "factorial [un número]" como factorización.

Realizar factorización:
Sea n el factorial del número entendido;
Diga "Es [n]".

C#:LINQ

    public static int factorial(int n)
    {
        return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
    }

Erlang:cola recursiva

fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).

fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).

Haskel:

ones = 1 : ones
integers   = head ones     : zipWith (+) integers   (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)

Mierda cerebral

+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]

Escrito por Michael Reitzenstein.

BÁSICO:vieja escuela

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

Lote (NT):

@echo off

set n=%1
set result=1

for /l %%i in (%n%, -1, 1) do (
    set /a result=result * %%i
)

echo %result%

Uso:C:>factorial.bat 15

F#:Funcional

Directo:

let rec fact x = 
    if   x < 0 then failwith "Invalid value."
    elif x = 0 then 1
    else x * fact (x - 1)

Poniéndose elegante:

let fact x = [1 .. x] |> List.fold_left ( * ) 1

Prólogo recursivo

fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.

Prólogo recursivo de cola

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).

rubí recursivo

(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1

uso:

factorial[5]
 => 120

Esquema

Aquí hay una definición recursiva simple:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

En Scheme, las funciones recursivas de cola utilizan un espacio de pila constante.Aquí hay una versión de factorial que es recursiva de cola:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

¿Ejemplos extraños?¿Qué pasa con el uso de la función gamma?Desde, Gamma n = (n-1)!.

OCaml:Usando gama

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)))

Programador novato de Haskell

fac n = if n == 0 
           then 1
           else n * fac (n-1)

Programador de estudiante de segundo año, en MIT (el esquema estudiado como estudiante de primer año)

fac = (\(n) ->
        (if ((==) n 0)
            then 1
            else ((*) n (fac ((-) n 1)))))

Programador Junior Haskell (Player de Peano principiante)

fac  0    =  1
fac (n+1) = (n+1) * fac n

Otro programador de Haskell junior (lea que los patrones N+K son "una parte asquerosa de Haskell" [1] y se unió al movimiento de "Ban N+K" -Movement [2])

fac 0 = 1
fac n = n * fac (n-1)

Programador Senior Haskell (votó por Nixon Buchanan Bush - "se inclina correctamente")

fac n = foldr (*) 1 [1..n]

Otro programador de Haskell senior (votó por McGovern Biafra Nader - "inclinado a la izquierda")

fac n = foldl (*) 1 [1..n]

¡Otro programador de Haskell senior (inclinado a la derecha a la derecha, volvió a la izquierda de nuevo!)

-- using foldr to simulate foldl

fac n = foldr (\x g n -> g (x*n)) id [1..n] 1

Memoizing Haskell Programador (toma a Ginkgo biloba diariamente)

facs = scanl (*) 1 [1..]

fac n = facs !! n

El programador de Haskell "sin sentido (ejem)" sin puntos "(estudiado en Oxford)

fac = foldr (*) 1 . enumFromTo 1

Programador de Haskell iterativo (ex programador de 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

Programador Iterativo de UNKELL (ex programador de APL y C)

fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))

Acumulación de programador Haskell (construyendo un clímax rápido)

facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)

fac = facAcc 1

El programador de Haskell de avance de la continuación (conejos elevados en los primeros años, luego se mudó a Nueva Jersey)

facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)

fac = facCps id

Programador de Boy Scout Haskell (le gusta atar nudos;siempre "reverente", pertenece a la iglesia del punto menos fijo [8])

y f = f (y f)

fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

Programador combinatorio de Haskell (evita las variables, si no la ofuscación;todo este curry es sólo una fase, aunque rara vez obstaculiza)

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)))

Programador de Haskell de codificación de listas (prefiere contar en unary)

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

Programador interpretativo de Haskell (nunca "conocí un lenguaje" que no le gustó)

-- 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)))

Programador estático Haskell (lo hace con clase, ¡tiene ese fondo Jones!Después de “Diversión con dependencias funcionales” de 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

Programador de posgrado inicial de Haskell (la educación de posgrado tiende a liberar a uno de las pequeñas preocupaciones sobre, por ejemplo, la eficiencia de los enteros basados en hardware)

-- 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

Programador origamista de Haskell (siempre comienza con el "pliegue de pájaros básicos")

-- (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

El programador de Haskell, incluido cartesianalmente (prefiere la comida griega, evita las cosas picantes indias;inspirado en “Clasificación de morfismos” de Lex Augusteijn [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)

Doctor.Programador de Haskell (comió tantos plátanos que sus ojos desecharon, ¡ahora necesita lentes nuevas!)

-- 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

Programador de Haskell postdoc (de Uustalu, Vene y Parkes de recursión de 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

Profesor titular (enseñando a Haskell a estudiantes de primer año)

fac n = product [1..n]

Plantillas D:Funcional

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);
}

Usado así:

factorial!(5)

Java 1.6:recursivo, memorizado (para llamadas posteriores)

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;
}

Potencia Shell

function factorial( [int] $n ) 
{ 
    $result = 1; 

    if ( $n -gt 1 ) 
    { 
        $result = $n * ( factorial ( $n - 1 ) ) 
    } 

    $result 
}

Aquí hay una sola línea:

$n..1 | % {$result = 1}{$result *= $_}{$result}

Intento:recursivo

En bash y recursivo, pero con la ventaja añadida de que trata cada iteración en un nuevo proceso.El máximo que puede calcular es !20 antes de desbordarse, pero aún puedes ejecutarlo para números grandes si no te importa la respuesta y quieres que tu sistema se caiga;)

#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow