En matemáticas una función recursiva es una función que se define en términos de sí misma. Hay muchos ejemplos, pero uno típico es la secuencia de Fibonacci, que se define así:
F(N) = F(N-1) + F(N-2)
Es decir, el número de Fibonacci de orden N es la suma de los números de órdenes N-1 y N-2. Como se puede observar, la secuencia se define en términos de sí misma.
Para que la definición esté completa hace falta una condición inicial, es decir, hace falta indicar el valor de los dos primeros números de Fibonacci, que son:
F(0) = 0 F(1) = 1
De este modo, es fácil calcular:
F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 F(5) = F(4) + F(3) = 3 + 2 = 5 F(6) = F(5) + F(4) = 5 + 3 = 8 F(7) = F(6) + F(5) = 8 + 5 = 13 …
En programación, igualmente, una función recursiva es una función que se llama a sí misma. Por ejemplo, el siguiente programa en C incluye la función recursiva int fibonacci(int n) que permite calcular la serie de Fibonacci:
Es importante empezar la función recursiva verificando las condiciones de terminación (¿n==0? ¿n==1?), porque si no se corre el riesgo de que el programa se meta en un bucle infinito.
Cuando un problema es de naturaleza recursiva, su programación de forma recursiva también suele resultar natural. No obstante, casi todo lo que se puede programar de forma recursiva también se puede programar de forma iterativa, es decir, usando bucles. Por ejemplo, la versión iterativa del mismo programa en C sería así:
¿Y todo esto a santo de qué viene? Pues que un árbol es una estructura de datos recursiva. Así que vamos a usar funciones recursivas para generar el árbol de juego.
¿Y se pueden hacer rutinas recursivas en ensamblador? Pues no es muy habitual, pero poderse se puede, y lo vamos a demostrar en las entradas que siguen.
No hay comentarios:
Publicar un comentario