Ejercicios de programación con recursividad y soluciones (codificados)

Recursividad

1.1. Introducción.

El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de bucles while, do-while, for, etc.

1.2. Definició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.
1.3. Elementos de la Recursión

1.3. 1. Axioma

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.

1.3.2. Formula recursiva

Relaciona el resultado del algoritmo 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.
Por ejemplo: El factorial de un número

factorial(0) -> 1
factorial(1) -> 1*factorial(0)
factorial(2) -> 2*factorial(1)
factorial(3) -> 3*factorial (2)
… -> …
factorial(N) -> 3*factorial (N-1)

En la resolución de algoritmos recursivos es imprescindible encontrar estos dos elementos.

1.4. Tipos de recursión

1.4.1. Recursividad simple

Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.

1.4.2. Recursividad múltiple
Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de hacer de forma iterativa. Un ejemplo típico es la función de fibonacci

1.4.3. Recursividad anidada
En algunos de los argumentos de la llamada recursiva hay una nueva llamada a sí misma. La función de Ackermann se define por recursividad como sigue:

1.4.4. Recursividad cruzada o indirecta
Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.

Planteamiento:

Ejercicio 1. Programar un algoritmo recursivo que calcule el factorial de un número.

Solución:

Código

----
int factorial(int n){
if(n==0) return 1; //AXIOMA
else return n*factorial(n-1); //FORMULA RECURSIVA
}
----
Planteamiento:

Ejercicio 2. Programar un algoritmo recursivo que calcule un número de la serie fibonacci.

Solución:

Código
----
int fibonaci(int n){
if(n==1 || n==2) return 1;
else return fibonaci(n-1)+fibonaci(n-2);
}
----
Planteamiento:

Ejercicio 3. Programar un algoritmo recursivo que permita hacer la división por restas sucesivas.

Solución:

Código
----
int division (int a, int b)
{
if(b > a) return 0;
else
return division(a-b, b) + 1;
}
----
Planteamiento:

Ejercicio 4. Programar un algoritmo recursivo que permita invertir un número. Ejemplo: Entrada: 123 Salida: 321

Solución:

Código
----
int invertir (int n)
{
if (n < n ="=" a="=" n ="=" tam ="=" b="=">0) return true;
else return negativo(n);
}

public boolean negativo(int n){
if(n<0) n="=" n="=" fila ="=" col ="=" fila ="=" col ="=" fila ="=" a="0," aux="1," b="0;" matriz =" new"> matriz.length -1){ //Si llegó a la ultima coluna, reseteamos los datos para la siguiente
i++;
j=0;
aux++;
}
if(i = (aux-1)){ //comprueba que estemos en el lugar adecuado, es decir ira imprimiento escaladamente
if(i==0)// si es la primera fila ingresamos aux=1
matriz[i][j] = matriz[i][j]=aux;
else
matriz[i][j] = matriz[i][i-1]*2;//ingresamos el valor correspondiente al ultimo de la "escala" *2
llenarMatriz(matriz, i , j+1);
}
else{ //si no, asignamos los valores anteriores de la escala
if(j==0)// comprobamos si es el primer digito a ingresar
matriz[i][j] = j+1;
else
matriz[i][j] = matriz[i-1][j];// asignamos el mismo numero de la fila anterior (i-1)
llenarMatriz(matriz, i, j+1);
}
}
}

public static void imprimir(){ //este metodo nos imprime la matriz por consola

for(int i=0; i< j="0;" c ="=" colmedio ="=" colmedio ="=" n ="="> x [n]) return x [0];
else return menor;
else
if (menor > x [n]) return menorvec (x, n - 1, x [n]);
else return menorvec (x, n - 1, menor); }
----
Planteamiento:

Ejercicio 17. Programar un algoritmo recursivo que muestre el numero mayor de un vector.

Solución:

Código
----
int mayor (int numeros [], int posicion) {
int aux;
if (posicion == 0) return numeros [posicion];
else {
aux = mayor (numeros, posicion - 1);
if (numeros [posicion] > aux) return numeros [posicion];
else return mayor (numeros, posicion - 1);
}
}
----

Autor: ·ohk·
http://foro.elhacker.net/ejercicios/ejercicios_recursivos_en_java_y_sus_soluciones-t231013.0.html

Agrego este material ya que permite ejemplificar claramente la recursividad y ahorrar código al programar, saludos.