Base de datos

I. INTRODUCCIÓN
La recursión permite definir un objeto en términos de sí mismo. Aparece eh numerosas actividades de la vida diaria; por ejemplo, en la fotografía de una fotografía. Casos típicos de estructuras de datos definidas de manera recursiva son las listas y los árboles. La recursividad es una propiedad esencial en el desarrollo de software; por esta razón, se analizan aquí ladescripción de la recursividad, así como el uso de algoritmos recursivos clásicos y complejos.

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.

Otra definición
Recurrencia, recursión o recursividad es laforma en la cual se especifica un proceso basado en su propia definición.

Elementos de la Recursividad
• 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.
• Formula recursiva: Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadasa la función, pero están más próximas al caso base.

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

Descripción
Implementación

int Factorial(int n){
if (n==0) { return 1; }
return n*Factorial(n-1);
}

Prueba de código



2. Programar un algoritmo recursivo que calcule un número de la serie Fibonacci.Descripción
Implementación

int Fibonacci(int n){
if (n == 0 || n == 1) { return 1; }
return Fibonacci(n-1) + Fibonacci(n-2);
}

Prueba de código








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

Descripción



Implementación

int Division(int a, int b){
if (b > a) { return 0; }
returnDivision(a-b, b) + 1;
}
Prueba de código


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

Descripción


Implementación

int Invertir(int n){
if (n < 10){ return n; }
return (n % 10) + Invertir(n / 10) * 10;
}
 
5. Programar un algoritmo recursivo que permita sumar los dígitos de un número. Ejemplo: Entrada: 123Resultado:6

Descripción


Implementación

int Sumar_Dig(int n){
if (n == 0){ return 0; }
return Sumar_Dig(n / 10 ) + ( n % 10 );
}
Ejemplo cuando n = 123

Sumar_Dig(123) = Sumar_Dig(123 / 10) + (123 % 10) = Sumar_Dig(12) + 3 = 3 + 3 = 6
Sumar_Dig(12) = Sumar_Dig(12/10) + (12 % 10) = Sumar_Dig(1) + 2 = 1 + 2 = 3
Sumar_Dig(1) = Sumar_Dig(1/10) + (1 % 10) =Sumar_Dig(0) + 1 = 0 + 1 = 1
Sumar_Dig(0) = 0

6. Programar un algoritmo recursivo que permita hacer una multiplicación, utilizando el método Ruso.

Descripción


Implementació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));
}
return (Mult_Rusa(A/2, B*2));
}

Ejemplo cuando A = 3y B = 5
Mult_Rusa(3,5) = 5 + Mult_Rusa(3/2 , 5*2) = 5 + 10 = 15
Mult_Rusa(1,10) = 10
 
7. Programar un algoritmo recursivo que permita sumar los elementos de un vector.

Descripción


Implementación

int Suma_Vec(int V[], int n){
if (n == 0){ return V[n]; }
return Suma_Vec(V, n-1) + V[n];
}
Ejemplo cuando V = {1,2,3} y n = 2

Suma_Vec(V,2) = 3 + Suma_Vec(V,2-1)= 3 + 3 = 6
Suma_Vec(V,1) = 2 + Suma_Vec(V,1-1) = 2 + 1 = 3
Suma_Vec(V,0) = 1



8. Programar un algoritmo recursivo que permita multiplicar los elementos de un vector.

Descripción


Implementación

int Multiplicar(int Vec[], int tam){
if (tam == 0){ return Vec[0]; }
return Vec[tam] * Multiplicar (Vec, tam-1);
}
Ejemplo cuando V = {2,4,1} y tam = 2...