Clase de Java Recursividad

RECURSIVIDAD

Un método es recursivo cuando se llama a si mismo ya sea directamente o indirectamente.

Si un método recursivo se invoca con un caso base, simplemente devuelve un resultado. Si el método se invoca con un problema más complejo, divide el problema en dos o más partes conceptuales: una parte del método sabe como resolver y una versión un poco más pequeña del problema original. Dado que este nuevo problema se asemeja al problema original, el método emite una llamada recursiva para trabajar con el problema reducido.

Para que la recursividad termine, cada vez que el método recursivo se llama a si mismo con una versión un poco más sencilla del problema original, la secuencia de problemas cada vez menores debe converger hacia el caso base. Cuando el método reconoce el caso base, devuelve el resultado a la llamada de método previa, y se inicia una secuencia de devoluciones que termina cuando la llamada del método original devuelve el resultado final.

RECURSIVIDAD VS ITERACION

Tanto la iteración como la recursión se basan en una estructura de control.: La iteración usa una estructura de repetición; la recursión una estructura de selección.

Tanto la iteración como la recursión implican repetición: la iteración emplea explícitamente una estructura de repetición; la recursión logra la repetición mediante llamadas de métodos repetidas

Tanto la iteración como la recursión incluyen una prueba de terminación; la iteración termina cuando deja de cumplirse la condición para continuar el ciclo; la recursión termina cuando se reconoce el caso base.

EJERCICIOS RESUELTOS


1) Hacer un programa para calcular el factorial de un número.


import java.util.Scanner;
 class Recursividad01{
   public static int factorial(int n)
   {
         if(n==0) return 1;
         else return n*factorial(n-1);
    }
   public static void main(String args[])
   {
        Scanner in =new Scanner(System.in);
        int num;
         do{
         System.out.print("Ingrese numero :");
         num=in.nextInt();
             }while(num<=0);
           System.out.println("El factorial es : "+factorial(num));

2) Calcular la potencia de x elevado a la n en forma recursiva. x real y n entero positivo


import java.util.Scanner;
 class Recursividad02{
  public static double potencia(double x, double n)
  {
     if(n==0) return 1;
     else return x*potencia(x,n-1);
   }
  public static void main(String args[])
  {
   Scanner in = new Scanner(System.in);
   int n;
   double x;
   System.out.print("Valor de x :");
   x= in.nextDouble();
   do{
   System.out.print("valor de n : ");
    n=in.nextInt();
   }while(n<=0);
   System.out.println(x+" elevado a la "+n+" es igual a "+potencia(x,n));
  }
}


3) Hacer un programa para que reporte los n términos de la serie de Fibonacci


import java.util.Scanner;
class Recursividad03{
public static int fibonacci(int n)
{
if(n==1) return 1;
else
if(n==2)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int n,i ;
do{
System.out.print("Número de terminos de la serie : ");
n=in.nextInt();
}while(n<=0);
for(i=1;i<=n;i++
System.out.print(fibonacci(i) + " ");
System.out.println();
}
}


4) Programa para calcular el máximo común divisor de dos números.


import java.util.Scanner;
class Recursividad04{
public static int mcd(int a,int b)
{
if(a%b==0) return b;
else return mcd(b,a%b);
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int x,y;
do{
System.out.print("Ingrese primer numero :");
x=in.nextInt();
}while(x<=0);
do{
System.out.print("Ingrese segundo numero :");
y=in.nextInt();
}while(y<=0);
System.out.println("El mcd de "+x+" y "+y+" es : "+mcd(x,y));
}
}


5) Programa para reportar un numero al reves


import java.util.Scanner;
class recursividad05{
public static void reves(int n)
{
System.out.print(n % 10);
if( n/10 !=0 ) reves(n/10);
}
public static void main(String args[]) throws IOException
{
Scanner in = new Scanner(System.in);
int num;
do{
System.out.print("Ingrese numero :");
num=in.nextInt();
}while(num<=0);
System.out.print("Numero al reves :");
reves(num);
System.out.println();
}
}


6) Programa para convertir un numero de base 10 a base b (entre 2 y 9)

import java.util.*;
class recursividad06{
public static void conversionBase(int n, int b)
{
if(n<b)
System.out.print(n);
else
{
conversionBase(n/b,b);
System.out.print(n%b);
}
}
public static void main(String args[]) throws IOException
{
Scanner in = new Scanner(System.in);
int num,b;
do{
System.out.print("Ingrese numero :");
num=Integer.parseInt(br.readLine());
}while(num<=0);
do{
System.out.print("Base a la que quiere convertir : ");
b=Integer.parseInt(br.readLine());
}while(b<2 || b>9);
System.out.print("El numero "+num+" en base "+b+" es : ");
conversionBase(num,b);
System.out.println();
}
}



EJERCICIOS PROPUESTOS

Usando métodos recursivos resolver los siguientes ejercicios
1) Calcular la suma de los n primeros números pares.
2) Calcular la suma de los n primeros números impares.
3) Calcular el producto de los dígitos de un numero
4) Verificar si todos los dígitos de un numero son iguales
5) Verificar si los dígitos de un numero están en escalera ascendentemente
6) Calcular el m.c.d. de dos números usando el algoritmo de Euclides.
7) Factorice por medio de la recursión. Por ejemplo si el numero es 8 sus factores serán 2x2x2
8) En un cuadrado cuyo lado es a, se unen los puntos medios de sus 4 lados, formándose otro cuadrado cuyos puntos medios se unen también formando otro cuadrado, y así sucesivamente. Calcular la suma de los perímetros de los n primeros cuadrados asi formados.
9) Calcule el m.c.,m de dos números.
10) En un vector de n elementos calcular el mayor de los elementos del Vector.
11) En un vector de n elementos calcular el producto de todos sus elementos.
12) Calcular la suma de los dígitos de un número.
13) Buscar un elemento en un vector de n elementos. Usando búsqueda secuencial.
14) Buscar un elemento en un vector de n elementos. Usando búsqueda binaria.
15) Calcular la longitud de una cadena.
16) Calcule el número de veces que aparece una letra en una cadena.
17) Contar el número de vocales que existe en una cadena