La Recursividad...

Definición

Recursión es una técnica de programación en el cual un método puede llamarse a sí mismo. Esto seguramente suena como algo raro de hacer o un grave error del que escribió esto. Sin embargo, la recursión una de las más interesantes y una de las técnicas sorprendentemente efectivas en programación.

Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.


En un algoritmo recursivo distinguimos como mínimo 2 partes:

* Caso trivial, base o de fin de recursión: Es la respuesta más sencila a un problema. Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.


* Parte puramente recursiva: Relaciona el resultado del problema con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.


EJEMPLO:


package Recursividad;
import java.util.Scanner;
/**
*
* @author pc132-25
*/
public class Fibonacci {
public int fibonnaci ( int n, int fibinf, int fibsup)
{
Scanner teclado = new Scanner (System.in);
System.out.println("Ingrese el numero");
n = teclado.nextInt();
System.out.println("--------------------");
if ((n==0) (n==1))
{
System.out.println("La suma es" +n);
return n;
}
fibinf = 0;
fibsup = 1;
for (int i =2; iint x;
x = fibinf;
fibinf = fibsup;
fibsup = x + fibinf;
System.out.println("" +fibsup);
}
return (fibsup);
}
public static void main(String[] args) {
Fibonacci fb = new Fibonacci();
int n = 0,fibinf = 0,fibsup = 1;
fb.fibonnaci(n, fibinf, fibsup);
}
　
long fibonacci (long n) {
if ( n== 0 n==1)
return n;
else
return fibonacci (n-1) + fibonacci (n-2);
}
}

*-*-*-*-**--*-*-*-*-*-*-*-*-*-*-*-*-*-**--*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Utilidad

Cuando la solución de un problema se puede expresar en términos de la resolución de un problema de la misma naturaleza, aunque de menor complejidad.

Sólo tenemos que conocer la solución no recursiva para algún caso sencillo (denominado caso base) y hacer que la división de nuestro problema acabe recurriendo a los casos base que hayamos definido. Como en las demostraciones por inducción, podemos considerar que “tenemos resuelto” el problema más simple para resolver el problema más complejo (sin tener que definir la secuencia exacta de pasos necesarios para resolver el problema).


Funcionamiento

- Se descompone el problema en problemas de menor complejidad (algunos de ellos de la misma naturaleza que el problema original).
- Se resuelve el problema para, al menos, un caso base.
- Se compone la solución final a partir de las soluciones parciales que se van obteniendo.


Diseño de algoritmos recursivos

1. Resolución de problema para los casos base:

• Sin emplear recursividad.
  


• Siempre debe existir algún caso base.
  

2. Solución para el caso general:

• Expresión de forma recursiva.



• Pueden incluirse pasos adicionales (para combinar las soluciones parciales).

Siempre se debe avanzar hacia un caso base: Las llamadas recursivas simplifican el problema y, en última instancia, los casos base nos sirven para obtener la solución.


int factorial (int n)
{

int resultado;

if (n==0) // Caso base
resultado = 1;

else // Caso general
resultado = n*factorial(n-1);
return (resultado);
}

int potencia (int base, int exp)
{

if (exp==0) // Caso base
return 1;

else // Caso general
return base * potencia(base,exp-1);
}


Recursividad vs. iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un problema (de forma iterativa o de forma recursiva):

- La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas.

- La redundancia (algunas soluciones recursivas resuelven un problema en repetidas ocasiones).

- La complejidad de la solución (en ocasiones, la solución iterativa es muy difícil de encontrar).

- La concisión, legibilidad y elegancia del código resultante de la solución recursiva del problema.


Ejemplo: Sucesión de Fibonacci


Fib (0) = Fib(1) = 1
Fib (n) = Fib(n - 1) + Fib (n - 2)

Solución recursiva
int fibonacci (int n)
{

if ((n == 0) (n == 1))
return 1;

else
return fibonacci(n-1) + fibonacci(n-2);
}


Ejemplo: Las torres de Hanoi



Mover n discos del poste 1 al poste 3 (utilizando el poste 2 como auxiliar):
hanoi (n, 1, 2, 3);

Solución recursiva:


void hanoi (int n, int inic, int tmp, int final)
{
if (n > 0) {

// Mover n-1 discos de "inic" a "tmp".
// El temporal es "final".

hanoi (n-1, inic, final, tmp);
// Mover el que queda en "inic" a "final"

printf (“Del poste %d al %d.\n”, inic, final);

// Mover n-1 discos de "tmp" a "final".
// El temporal es "inic".

hanoi (n-1, tmp, inic, final);
}
}







Según la leyenda, los monjes de un templo tenían que mover una pila de 64 discos sagrados de un sitio a otro. Sólo podían mover un disco al día y, en el templo, sólo había otro sitio en el que podían dejarlos, siempre ordenados de forma que los mayores quedasen en la base.
El día en que los monjes realizasen el último movimiento, el final del mundo habría llegado…