recursion - programacion - ¿Qué idiomas admiten*funciones recursivas*literales/funciones anónimas?

funciones recursivas matematicas discretas

Question

Parece que algunos idiomas principales admiten literales de funciones en estos días. También se llaman funciones anónimas , pero no me importa si tienen un nombre. Lo importante es que una función literal es una expresión que produce una función que no ha sido definida en otro lugar, por ejemplo en C, &printf no cuenta.

EDITAR para agregar: si tiene una expresión literal de función genuina <exp> , debería poder pasarla a una función f(<exp>) o aplicarla inmediatamente a un argumento, es decir. <exp>(5) .

Tengo curiosidad por saber qué idiomas te permiten escribir literales de funciones que son recursivos . El artículo de " recursión anónima " de Wikipedia no da ningún ejemplo de programación.

Usemos la función factorial recursiva como ejemplo.

Estos son los que yo sé:

• JavaScript / ECMAScript puede hacerlo con el callee :

  function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}}

• es fácil en idiomas con letrec , por ejemplo, Haskell (que lo llama let ):

  let fac x = if x<2 then 1 else fac (x-1) * x in fac

  y hay equivalentes en Lisp y Scheme. Tenga en cuenta que el enlace de fac es local a la expresión, por lo que la expresión completa es, de hecho, una función anónima.

¿Hay otros?

Answer 1

Creo que esto puede no ser exactamente lo que estás buscando, pero en Lisp, las "etiquetas" se pueden usar para declarar dinámicamente funciones que se pueden llamar recursivamente.

(labels ((factorial (x) ;define name and params
    ; body of function addrec
    (if (= x 1)
      (return 1)
      (+ (factorial (- x 1))))) ;should not close out labels
  ;call factorial inside labels function
  (factorial 5)) ;this would return 15 from labels

Answer 2

Delphi incluye las funciones anónimas con la versión 2009.

Ejemplo de http://blogs.codegear.com/davidi/2008/07/23/38915/

type
  // method reference
  TProc = reference to procedure(x: Integer);               

procedure Call(const proc: TProc);
begin
  proc(42);
end;

Utilizar:

var
  proc: TProc;
begin
  // anonymous method
  proc := procedure(a: Integer)
  begin
    Writeln(a);
  end;               

  Call(proc);
  readln
end.

Answer 3

La mayoría de los idiomas lo admiten mediante el uso del combinador Y. Aquí hay un ejemplo en Python (del libro de cocina ):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040

Answer 4

Puedes hacerlo en Perl:

my $factorial = do {
  my $fac;
  $fac = sub {
    my $n = shift;
    if ($n < 2) { 1 } else { $n * $fac->($n-1) }
  };
};

print $factorial->(4);

El bloque do no es estrictamente necesario; Lo incluí para enfatizar que el resultado es una verdadera función anónima.

Answer 5

F # tiene "let rec"

Answer 6

DO#

Al leer el blog de Wes Dyer , verás que la respuesta de @Jon Skeet no es del todo correcta. No soy un genio en idiomas, pero hay una diferencia entre una función anónima recursiva y la " función fib simplemente invoca al delegado al que hace referencia la variable local fib " para citarlo en el blog.

La respuesta real de C # se vería así:

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
} 

Answer 7

En Perl 6:

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000

Answer 8

Como tenía curiosidad, en realidad traté de encontrar una forma de hacerlo en MATLAB . Se puede hacer, pero se ve un poco Rube-Goldberg-esque:

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120

Answer 9

Puede hacerlo en Matlab usando una función anónima que utiliza la introspección dbstack () para obtener la función literal de sí misma y luego evaluarla. (Admito que esto es una trampa porque dbstack probablemente debería considerarse extralingüístico, pero está disponible en todos los Matlabs).

f = @(x) ~x || feval(str2func(getfield(dbstack, ''name'')), x-1)

Esta es una función anónima que realiza una cuenta regresiva desde xy luego devuelve 1. No es muy útil porque Matlab carece del operador?: Y no permite bloques dentro de funciones anónimas, por lo que es difícil construir el caso base / forma de paso recursivo.

Puede demostrar que es recursivo llamando a f (-1); contará hacia abajo hasta el infinito y eventualmente arrojará un error máximo de recursión.

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,''RecursionLimit'',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Y puede invocar la función anónima directamente, sin vincularla a ninguna variable, pasándola directamente a feval.

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, ''name'')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,''RecursionLimit'',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,''name'')),x-1)

Para hacer algo útil a partir de él, puede crear una función separada que implemente la lógica de paso recursiva, usando "si" para proteger el caso recursivo de la evaluación.

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

Dado que, aquí es factorial.

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, ''name'')),...
    {x-1},...
    @(z)x*z);

Y puedes llamarlo sin ataduras.

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, ''name'')), {x-1}, @(z)x*z), 5)
ans =
   120

Answer 10

Existen funciones anónimas en C ++ 0x con lambda, y pueden ser recursivas, aunque no estoy seguro de que sean anónimas.

auto kek = [](){kek();}

Answer 11

''Parece que tienes la idea de que las funciones anónimas están equivocadas, no se trata solo de la creación en tiempo de ejecución, sino también del alcance. Considere esta macro Scheme:

(define-syntax lambdarec
  (syntax-rules ()
    ((lambdarec (tag . params) . body)
     ((lambda ()
       (define (tag . params) . body)
        tag)))))

Tal que:

(lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))

Evalúa una verdadera función factorial recursiva anónima que puede, por ejemplo, usarse como:

(let ;no letrec used
    ((factorial (lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))))
  (factorial 4)) ; ===> 24

Sin embargo, la verdadera razón que lo hace anónimo es que si lo hago:

((lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1))))) 4)

La función es luego borrada de la memoria y no tiene alcance, por lo tanto después de esto:

(f 4)

Señalará un error o se vinculará a lo que f estaba vinculado antes.

En Haskell, una forma ad hoc para lograr lo mismo sería:

/n -> let fac x = if x<2 then 1 else fac (x-1) * x
    in fac n

La diferencia nuevamente es que esta función no tiene alcance, si no la uso, con Haskell siendo Lazy el efecto es el mismo que una línea vacía de código, es verdaderamente literal ya que tiene el mismo efecto que el código C:

3;

Un número literal. E incluso si lo uso inmediatamente después, desaparecerá. De esto se tratan las funciones literales, no la creación en tiempo de ejecución per se.

Answer 12

También parece que Mathematica le permite definir funciones recursivas usando #0 para denotar la función en sí, como:

(expression[#0]) &

por ejemplo, un factorial:

fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;

Esto está de acuerdo con la notación #i para referirse al parámetro ith, y la convención de shell-scripting de que un script es su propio 0º parámetro.

Answer 13

Clojure puede hacerlo, ya que fn toma un nombre opcional específicamente para este propósito (el nombre no escapa al alcance de la definición):

> (def fac (fn self [n] (if (< n 2) 1 (* n (self (dec n))))))
#''sandbox17083/fac
> (fac 5)
120
> self
java.lang.RuntimeException: Unable to resolve symbol: self in this context

Si se trata de recursividad de cola, recur es un método mucho más eficiente:

> (def fac (fn [n] (loop [count n result 1]
                     (if (zero? count)
                       result
                       (recur (dec count) (* result count))))))

Answer 14

Aquí has ​​mezclado algo de terminología, los literales de funciones no tienen que ser anónimos.

En JavaScript, la diferencia depende de si la función se escribe como una declaración o una expresión. Hay alguna discusión sobre la distinción en las respuestas a esta pregunta .

Digamos que estás pasando tu ejemplo a una función:

foo(function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}});

Esto también podría escribirse:

foo(function fac(n){if (n<2) {return 1;} else {return n * fac(n-1);}});

En ambos casos, es una función literal. Pero tenga en cuenta que en el segundo ejemplo, el nombre no se agrega al ámbito circundante, lo que puede ser confuso. Pero esto no se usa ampliamente, ya que algunas implementaciones de JavaScript no son compatibles con esto o tienen una implementación incorrecta. También he leído que es más lento.

La recursión anónima es algo diferente otra vez, es cuando una función recurre sin tener una referencia a sí misma, el Combinador Y ya ha sido mencionado. En la mayoría de los idiomas, no es necesario ya que hay mejores métodos disponibles. Aquí hay un enlace a una implementación de javascript .

Answer 15

Bueno, aparte de Common Lisp ( labels ) y Scheme ( letrec ) que ya has mencionado, JavaScript también te permite nombrar una función anónima:

var foo = {"bar": function baz() {return baz() + 1;}};

que puede ser más callee que usar callee . (Esto es diferente de la function en el nivel superior, lo último haría que el nombre aparezca también en el ámbito global, mientras que en el primer caso, el nombre aparece solo en el alcance de la función).

Answer 16

En C # necesita declarar una variable para retener al delegado y asignarle un valor nulo para asegurarse de que esté definitivamente asignada, luego puede llamarlo desde dentro de una expresión lambda que le asigne:

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

Creo que escuché rumores de que el equipo de C # estaba considerando cambiar las reglas sobre la asignación definitiva para hacer innecesaria la declaración / inicialización por separado, pero no lo juraría.

Una pregunta importante para cada uno de estos lenguajes / entornos de tiempo de ejecución es si admiten llamadas finales. En C #, hasta donde yo sé, el compilador de MS no usa la tail. IL opcode, pero el JIT puede optimizarlo de todos modos, en ciertas circunstancias . Obviamente, esto puede marcar la diferencia entre un programa que funcione y un desbordamiento de pila. (Sería bueno tener más control sobre esto y / o garantías sobre cuándo ocurrirá. De lo contrario, un programa que funciona en una máquina puede fallar en otra de una manera difícil de entender).

Editar: como FryHard señaló, esto es solo pseudo-recursión. Lo suficientemente simple para hacer el trabajo, pero el Y-combinator es un enfoque más puro. Hay otra advertencia con el código que publiqué arriba: si cambias el valor de fac , todo lo que intente usar el valor anterior comenzará a fallar, porque la expresión lambda ha capturado la variable fac . (Lo que tiene que hacer para funcionar correctamente, por supuesto ...)