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) -> N*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:
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:
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:
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:
Planteamiento:
Ejercicio 11. Programar un algoritmo recursivo que determine si un número es impar utilizando recursividad cruzada.
Solución:
Planteamiento:
Ejercicio 12. Programar un algoritmo recursivo que permita sumar los elementos de una matriz.
Solució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) -> N*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:
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:
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:
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:
int invertir (int n){
if (n < 10) //caso base
return n;
else
return (n % 10) + invertir (n / 10) * 10;
}
if (n < 10) //caso base
return n;
else
return (n % 10) + invertir (n / 10) * 10;
}
Planteamiento:
Ejercicio 5. Programar un algoritmo recursivo que permita sumar los dígitos de un número. Ejemplo: Entrada: 123 Resultado:6
Solución:
Ejercicio 5. Programar un algoritmo recursivo que permita sumar los dígitos de un número. Ejemplo: Entrada: 123 Resultado:6
Solución:
int sumar_dig (int n)
{
if (n == 0) //caso base
return n;
else
return sumar_dig (n / 10) + (n % 10);
}
{
if (n == 0) //caso base
return n;
else
return sumar_dig (n / 10) + (n % 10);
}
Planteamiento:
Ejercicio 6. Programar un algoritmo recursivo que permita hacer una multiplicación, utilizando el método Ruso. Para mas informacion: aqui.
Solución:
Ejercicio 6. Programar un algoritmo recursivo que permita hacer una multiplicación, utilizando el método Ruso. Para mas informacion: aqui.
Solución:
int mult_rusa(int A, int B)
{
if(A==1){
return (B);
}
if(A%2!=0){
return(B+mult_rusa( A/2 , B*2));
}
else{
return(mult_rusa( A/2 , B*2));
}
}
{
if(A==1){
return (B);
}
if(A%2!=0){
return(B+mult_rusa( A/2 , B*2));
}
else{
return(mult_rusa( A/2 , B*2));
}
}
Planteamiento:
Ejercicio 7. Programar un algoritmo recursivo que permita sumar los elementos de un vector.
Solución:
Ejercicio 7. Programar un algoritmo recursivo que permita sumar los elementos de un vector.
Solución:
int suma_vec(int v [], int n)
{
if (n == 0)
return v [n];
else
return suma_vec(v, n - 1) + v [n];
}
{
if (n == 0)
return v [n];
else
return suma_vec(v, n - 1) + v [n];
}
Planteamiento:
Ejercicio 8. Programar un algoritmo recursivo que permita multiplicar los elementos de un vector.
Solución:
Ejercicio 8. Programar un algoritmo recursivo que permita multiplicar los elementos de un vector.
Solución:
int multiplicar (int vec [], int tam)
{
if (tam == 0)
return (vec [0]);
return (vec [tam] * multiplicar (vec, tam - 1));
}
{
if (tam == 0)
return (vec [0]);
return (vec [tam] * multiplicar (vec, tam - 1));
}
Planteamiento:
Ejercicio 9. Programar un algoritmo recursivo que calcule el Maximo comun divisor de dos números.
Solución:
Ejercicio 9. Programar un algoritmo recursivo que calcule el Maximo comun divisor de dos números.
Solución:
int sacar_mcd(int a, int b) {
if(b==0)
return a;
else
return sacar_mcd(b, a % b);
}
if(b==0)
return a;
else
return sacar_mcd(b, a % b);
}
Planteamiento:
Ejercicio 10. Programar un algoritmo recursivo que determine si un número es positivo.
Solución:
Ejercicio 10. Programar un algoritmo recursivo que determine si un número es positivo.
Solución:
public boolean positivo(int n){
if(n>0) return true;
else return negativo(n);
}
public boolean negativo(int n){
if(n<0) return false;
else return positivo(n);
}
if(n>0) return true;
else return negativo(n);
}
public boolean negativo(int n){
if(n<0) return false;
else return positivo(n);
}
Planteamiento:
Ejercicio 11. Programar un algoritmo recursivo que determine si un número es impar utilizando recursividad cruzada.
Solución:
public boolean par(int n){
if(n==0)
if(n==0)
return true;
else
else
return impar(n-1);
}
public boolean impar(int n){
if(n==0)
}
public boolean impar(int n){
if(n==0)
return false;
else
else
return par(n-1);
}
}
Ejercicio 12. Programar un algoritmo recursivo que permita sumar los elementos de una matriz.
Solución:
int suma (int fila, int col, int orden, int mat [] [])
{
if (fila == 0 && col == 0)
return mat [0] [0];
else
if (col < 0)
return suma (fila - 1, orden, orden, mat);
else
return mat [fila] [col] + suma (fila, col - 1, orden, mat);
}
{
if (fila == 0 && col == 0)
return mat [0] [0];
else
if (col < 0)
return suma (fila - 1, orden, orden, mat);
else
return mat [fila] [col] + suma (fila, col - 1, orden, mat);
}
Planteamiento:
Ejercicio 13. Programar un algoritmo recursivo que permita resolver el cuadro latino. Ejemplo de cuadro latino:
0 0 0 0 1
0 0 0 1 2
0 0 1 2 3
0 1 2 3 4
1 2 3 4 5
Solución:
Ejercicio 13. Programar un algoritmo recursivo que permita resolver el cuadro latino. Ejemplo de cuadro latino:
0 0 0 0 1
0 0 0 1 2
0 0 1 2 3
0 1 2 3 4
1 2 3 4 5
Solución:
latino (int fila, int col, int cont, int orden, int mat [] [])
{
if (fila == 0 && col == 0)
mat [0] [0] = 1;
else
if (fila == col)
latino (fila - 1, orden - 1, orden, orden, mat);
else
{
mat [fila] [col] = cont;
latino (fila, col - 1, orden + 1, orden, mat);
}
}
{
if (fila == 0 && col == 0)
mat [0] [0] = 1;
else
if (fila == col)
latino (fila - 1, orden - 1, orden, orden, mat);
else
{
mat [fila] [col] = cont;
latino (fila, col - 1, orden + 1, orden, mat);
}
}
Planteamiento:
Ejercicio 16. Programar un algoritmo recursivo que muestre el numero menor de un vector.
Solución:
Ejercicio 16. Programar un algoritmo recursivo que muestre el numero menor de un vector.
Solución:
int menorvec (int x [], int n, int menor) {
if (n == 0)
if (menor > 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); }
if (n == 0)
if (menor > 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:
Ejercicio 17. Programar un algoritmo recursivo que muestre el numero mayor de un vector.
Solución:
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);
}
}
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);
}
}
Comentarios
Publicar un comentario