CONCEPTOS BÁSICOS

• Un objeto es recursivo cuando se define 

en función de sí mismo, es decir, interviene 

en su propia definición.

• La recursividad es la propiedad mediante 

la cual un subprograma o rutina puede 

llamarse a sí mismo.

• Utilizando la recursividad, la resolución de 

un problema se reduce a uno esencialmente 

igual pero algo menos complejo.

• Características que deben cumplir los 

problemas recursivos:

– La recursividad debe terminar alguna vez: caso 

base

– Cada nueva formulación estamos más cerca 

del caso final (o base).EJEMPLO DE PRO

 

 

 

 

 

 

 

Problema 1:

Implementación de un método recursivo.

Programa:

public class Recursividad { void repetir() { repetir(); } public static void main(String[] ar) { Recursividad re=new Recursividad(); re.repetir(); } }

La función repetir es recursiva porque dentro de la función se llama a sí misma.
Cuando ejecuta este programa se bloqueará y generará una excepción: "Exception in thread "main" java.lang.StackOverflowError"

Analicemos como funciona:
Primero se ejecuta la función main, luego de crear un objeto llamamos a la función repetir.
Hay que tener en cuenta que cada vez que se llama a una función se reservan 4 bytes de la memoria que se liberarán cuando finalice su ejecución.
La primera línea de la función llama a la función repetir, es decir que se reservan 4 bytes nuevamente. Se ejecuta nuevamente una instancia de la función repetir y así sucesivamente hasta que la pila estática se colme y se cuelgue el programa.

Problema 2:

Implementación de un método recursivo que reciba un parámetro de tipo entero y luego llame en forma recursiva con el valor del parámetro menos 1.

Programa:

public class Recursividad { void imprimir(int x) { System.out.println(x); imprimir(x-1); } public static void main(String[] ar) { Recursividad re=new Recursividad(); re.imprimir(5); } }

Desde la main se llama a la función imprimir y se le envía el valor 5. El parámetro x recibe el valor 5. Se ejecuta el algoritmo de la función, imprime el contenido del parámetro (5) y seguidamente se llama a una función, en este caso a sí misma (por eso decimos que es una función recursiva), enviándole el valor 4.
El parámetro x recibe el valor 4 y se imprime en pantalla el cuatro, llamando nuevamente a la función imprimir enviándole el valor 3.
Si continuamos este algoritmo podremos observar que en pantalla se imprime:

5 4 3 2 1 0 ?1 ?2 ?3 . . . . . . . . .

hasta que se bloquee el programa.Tener en cuenta que cada llamada a una función consume 4 bytes por la llamada y en este caso 4 bytes por el parámetro x. Como nunca finaliza la ejecución completa de las funciones se desborda la pila estática por las sucesivas llamadas.

 

Problema 3:

Implementar un método recursivo que imprima en forma descendente de 5 a 1 de uno en uno.

Programa:

public class Recursividad { void imprimir(int x) { if (x>0) { System.out.println(x); imprimir(x-1); } } public static void main(String[] ar) { Recursividad re=new Recursividad(); re.imprimir(5); } }

Ahora si podemos ejecutar este programa y observar los resultados en pantalla. Se imprimen los números 5 4 3 2 1 y no se bloquea el programa.
Analice qué sucede cada vez que el if (x>0) se evalúa como fal