miércoles, noviembre 21, 2007

Lisp, por fin algo útil y potente como la recursividad

¿Que es la recursión, o recursividad?

Podemos decir que es una forma de resolver problemas.

Si analizamos un problema, y descubrimos que se puede resolver por partes en las que se vuelve a plantear el problema original pero de forma más "reducida", entonces podemos resolver por recursión.

Ya veis que es algo dificil de explicar, pero se puede ver muy fácilmente.

El ejemplo típico es la función factorial.

El factorial de 6 se representa: 6! y es igual a 6 x 5 x 4 x3 x 2 x 1. Por lo tanto 6! = 720.

Si nos fijamos un poco podemos ver que el factorial de 5 es igual a 5 x 4 x 3 x 2 x 1.

Por lo tanto el factorial de 6 es igual a 6 x el factorial de 5.
Y el factorial de 5 es igual a 5 x el factorial de 4.
etc. etc.

Por convenio en matemáticas el factorial de 0 es igual a 1.

Vemos que podemos usar la función factorial al intentar calcular el factorial de un número.

Función factorial recursiva:

(defun factorial (n)
(if (zerop n) 1
(* n (factorial (1- n)))
)

)

Explicación de la función:

El factorial de un número n es:
1-Si n = 0 entonces el factorial es 1.
2-Si n no es 0, entonces el factorial es n x factorial(n-1)

Avisos:
La función (1- n) devuelve el número n menos 1.
Existe la función (1+ n) que devuelve el número n más 1.

1 comentario:

Carlos Calderon G dijo...

Muy clara la explicación de recursividad, con el caso del factorial...