En programación, una función es recursiva cuando se llama a sí misma.
Uno de los ejemplos más clásicos es el factorial de un número. Intenta seguir la explicación razonando cada paso. Para cualquier entero positivo N, el factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los enteros menor a él:
- 1! = 1
- 2! = 1 x 2 = 2
- 3! = 1 x 2 x 3 = 6
- 4! = 1 x 2 x 3 x 4 = 24
- 5! = 1 x 2 x 3 x 4 x 5 = 120
- 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720
“2!” es “1[1!] x 2″
“3!” es “(1 x 2)[2!] x 3″
Y así sucesivamente. Para cualquier entero N mayor a 1, podemos decir que el factorial de N es igual al factorial del número anterior a N multiplicado por N. La fórmula N! = (N-1)! x N. Vuelve a la lista de factoriales de 1 a 6. Busca en cada caso los términos que son factorial del número anterior para darte cuenta. Entonces se podria decir que una buena practica es encontrar el factor en el resultado que se repite.
Pasando ésto a función en C, podemos hacer una función a la que le pasamos un número, y nos devuelve el factorial:
El problema es que la función definida arriba no termina nunca, va a seguir restándole 1 a N por siempre. Siempre vamos a poder restarle 1 a cualquier n, por lo que la función va a seguir ejecutándose a sí misma por siempre. Además, para cualquier número positivo, factorial de n va a devolver 0, porque cualquier multiplicación con 0 como término devuelve 0. Y restarle 1 recursivamente a cualquier entero positivo, eventualmente dará cero.
Para que la función recursiva esté completa, además de llamarse a sí misma, necesita una forma de finalizar, una condición.
Por definición, el factorial de 1 es 1 (1!=1) así como el factorial de 0 (0!=1)también es 1. Por lo que podemos implementar ésta condición para que la función no sea interminable.
Así, la definición de la función consta de la recursiva que se llama a sí misma, y la condición para detenerse.
O con un while:
Y bueno, este fue mi intento por explicar qué es la recursividad en la programación y cómo funciona con un ejemplo. Otro buen ejemplo es la serie de Fibonacci, pero ésta da para un estudio más a fondo, ya que tiene bastantes cosas interesantes. También es interesante la Torre de Hanoi, resulta bastante interesante y clásico a la hora de aplicar recursividad.
REFERENCIAS:
http://www.algoritmia.net/articles.php?id=11
http://es.wikipedia.org/wiki/Recursi%C3%B3n
http://picandocodigo.net/2008/recursividad-en-programacion/
Bien, 4 puntos.
ResponderEliminar