Recursividad(n-1)

La clase de hoy de Estructuras estuvo más entretenida que de costumbre. ¿Cambios radicales en la materia? No. es que el tema de hoy fue recursividad, recursión o como le digan (si es que le dicen de alguna manera), ¿Y que puede haber de no-divertido en funciones que se llaman a si mismas?

Es natural tenerle miedo a las funciones recursivas antes de conocerlas, uno piensa “¿Cómo? ¡si se llama a si misma nunca termina!, ¡se nos llega a meter una de esas malditas cosas en ‘el sistema’ y lo deja caido para siempre!¡va a haber saqueos, muerte y destrucción por doquier!”.
Pero a tranquilizarse, eso no pasa, a menos que los programadores no sepan nada de esta técnica. En ese caso recomiendo comprarse un búnker nuclear, aunque teniendo en cuenta el elevado precio que han adquirido estos refugios gracias a la inflación, mejor consideremos las siguientes alternativas:

1) Eliminar las computadoras de la faz de la Tierra.
2) Acordarse las tres reglas fundamentales e indiscutibles de la recursividad.

Dado que la primera opción implica un futuro en el que no tengo trabajo, mejor elijamos la segunda.

Reglas fundamentales, absolutas, inalienables e indiscutibles de la recursión

  1. Saber cuándo parar: esta regla es aplicable a muchas esferas de la vida, pero en funciones recursivas es muy importante. Si no se especifica una condición de terminación (o como me enteré hoy que le decían, caso degenerado), la función puede entrar en una recursión infinita, cosa que muy probablemente desatará las tragedias anteriormente mencionadas.
  2. Saber cómo dar el paso: sí, en la vida es muy difícil dar el gran paso, pero en las funciones recursivas no es la gran cosa. Se refiere a obtener, devolver o modificar algún valor, que es parte de la solución del problema. (se va a ver más claro en el ejemplo)
  3. Reducir: no hay demasiado misterio en esta regla. La función se llama a sí misma enviándose una entrada menor a la que recibió. Ojalá fuera tan fácil reducir los problemas de uno.

ej1. La ultraquemada sumatoria (ej. Sumatoria de 5 = 1 + 2 + 3 + 4 + 5)

C#:
public int Sumatoria(int n)
{
//Caso degeneradísimo
if (n == 1)
return 1;
else
//Paso adelante y reducción.
return n + Sumatoria(n – 1);
}

Sigamos el caso de 4 (ya tengo las manos cansadas):
Sumatoria(4) = 4 + Sumatoria(3)
Sumatoria(3) = 3 + Sumatoria(2)
Sumatoria(2) = 2 + Sumatoria(1)
Sumatoria(1) = 1

Si reemplazamos cada llamada a la función por el valor que devolvió, obtenemos 10. ¡Voilá!

ej2. Decidir si un elemento es miembro de una lista. (no es a propósito lo del nombre de la función, me acabo de dar cuenta)

Lisp:
(defun mi-miembro (x lista)
(cond
((null lista) nil)
((equal x (first lista)) T)
(T (mi-miembro (rest lista)))
)
)


Como diría algún profesor que ya no tiene ganas de explicar: identificar las tres reglas en el ejemplo anterior queda de ejercicio.

Por hoy me voy despidiendo, pero antes quería aclarar que estos son solamente algunos de los tipos de funciones recursivas, ¡todavía quedan muchas con las cuales divertirse! ;)

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: