Recursividad

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
returndivision(a-b, b) + 1;
}

División mediante Restas
1. Introducción: La División como todos la conocemos, es una operación en la cual tratamos de buscar el producto que multiplicado por el divisor, dé el dividendo o lo más parecido a este.
Ejemplo:
5 / 2 = 2 (2 x 2= 4), con residuo de 1 (5 - 4 = 1)
Sin embargo, la división no es mecánica. Existe todo un proceso, de restas por la cualobtenemos un resultado.
2. Explicación: Las computadoras solo pueden restar y sumar. Para multiplicar, suman progresivamente y para dividir… (Supongo ya lo habrás adivinado) restan progresivamente.
Veámoslo con el ejemplo del 5 / 2. Tenemos los siguientes datos:
• Dividendo: 5
• Divisor: 2
• Cociente: 2
• Residuo: 1
Ahora veamos las restas sucesivas:
5 - 2 = 3
3 - 2 = 1
Como verás se haido restando del dividendo, el divisor y la operación se repite hasta que el resultado ya no sea mayor que el divisor o menor que 0. El resultado de la última resta es el residuo y la cantidad de restas realizadas es el cociente. Nótese que el cociente es 2 y en total hay 2 restas.


________________________________________

Planteamiento:

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

Solución:
Código
int invertir (int n)
{
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:
Código
int sumar_dig (int n)
{
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:
Códigoint 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));
}
}

Los rusos no tenían necesidad de aprenderse la tabla. Solo necesitaban saber sumar y hacer mitades. Veamos primero un ejemplo sencillo: 24×8. Para realizar esta multiplicación,escribían dos columnas, una con el 24 y otra con el 8. Una columna la van doblando y la otra la van partiendo a la mitad:
24 1
48 2
96 4
192 8
Como una columna se ha ido doblando y la otra partiendo por la mitad, los productos 24×8, 48×4, 96×2 y 192×1 son iguales. Como la tabla del 1 sí se la habían aprendido y 192×1=192, resulta que 24×8 da 192.
¿Qué ocurre si en la columna en la quedividimos sale un número impar? Pues también pensaron en eso. Si sale un número impar, le restan 1 para que sea par y siguen con el método, pero haciendo una marca en esa fila. Al final, suman al resultado los números marcados y obtienen en resultado de la multiplicación. Un ejemplo es más útil: 31×18
31 18
–> 62 9 (8) 496
124 4 + 62
248 2 _______
496 1 558
Por lo tanto, 31×18 son 558.
El...