Problemas

de Recursividad
Problema 1.
El factorial de un nmero entero ! 0, denotado como !!, se define como ! ! !! ! = 1 2 ! cuando ! > 0, y 0! = 1. Por ejemplo 6! = 1 2 3 4 5 6 = 720 Disead una mtodo recursiva que lo calcule e implementadlo en Java (junto con un programa que lo utilice)

Problema 2. .
Para calcular el mximo comn divisor de dos nmeros enteros puedo aplicar el algoritmo de Euclides, que consiste en ir restando el ms pequeo del ms grande hasta que queden dos nmeros iguales, que sern el mximo comn divisor de los dos nmeros. Por ejemplo, si comenzamos con el par de nmeros 412 y 184, tendramos: 412 228 44 44 44 44 44 36 28 20 12 8 4 184 184 184 140 96 52 8 8 8 8 8 4 4 Es decir, m.c.d.(412, 184) = 4

Problema 3.

Disear un mtodo recursivo tal que dado un vector de nmeros enteros retorne la suma de sus elementos. Para poder hacer recursividad, usaremos un ndice que indique el trozo de vector a sumar en cada llamada. Es decir, el mtodo a disear tendr la forma:
1 public int sum(int[] elems, int pos) { 2 ? 3 }

Disead este mtodo as como el que lo utiliza para calcular la suma de todo el vector. Tened en cuenta cmo hacemos para referirnos a un intervalo dentro de un vector. Qu pasa si el vector est vaco (es decir, cuando [Link] vale cero)? Usando el mtodo recursivo, implementad el mtodo que lo usa para calcular la suma de todo el vector, es decir:
4 public int sum(int[] elems) { 5 return sum(elems, ?); 6 }

Nota: Podis considerar dos descomposiciones del vector, una en la que la zona que vais sumando crece de derecha a izquierda y otra en la que lo hace en sentido contrario.

Problema 4.
Disead un mtodo recursivo que escriba al revs la cadena que se le pasa como parmetro, ms un ndice que se usar para recorrer la cadena. Dicho mtodo ser de la forma:
1 public void printReversed(String text, int index) { 2 ? 3 }

Haced dos versiones del mismo, una en la que el ndice vaya incrementndose a cada llamada y otra en la ste que vaya decrementndose. En los dos casos implementad la funcin que llama a la funcin recursiva diseada, es decir:
4 public void printReversed(String text) { 5 printReversed(text, ?); 6 }

Nota: No vale invertir la cadena y luego escribirla.

Problema 5.
El ejemplo de la exponenciacin mostrado en los apuntes, permite la siguiente descomposicin: ! Si b es par, !! = !!(! div 2) = !! div 2 Si b es impar, !! = !!(! div 2)+1 = ! !! div 2 Acabad de disear la solucin recursiva que la emplea, implementar la solucin en Java y hacer el mismo diagrama de llamadas para el caso de 7!" . Nota: Es muy interesante que intentis resolver un mismo problema de varias maneras y comparis entre s las diferentes soluciones.
!

Problema 6.
Ya que estamos, disead un mtodo tal que dada una cadena, retorne la cadena invertida (es decir, el primer carcter del resultado ser el ltimo de la cadena dada, etc.). Dicho mtodo tendr la forma:
1 public String invert(String text) { 2 ? 3 }

Para hacerlo, debis disear otro tal que dado un vector de caracteres, lo invierta. Como los parmetros que son vectores se pasan por referencia, el mtodo invert sobre vectores puede ser de la forma:
1 public void invert(char[] textChars) { 2 ? 3 }

Para encontrar recursividad deberis hacer otro mtodo que, adems del char[], use uno o ms ndices sobre el vector.

Problema 7.
Disead un mtodo tal que, dados dos vectores de enteros, retorne un booleano indicando si son iguales, es decir, si tienen los mismos valores en las mismas posiciones. Para poder hacerlo recursivamente deberis, como ya es habitual, hacer otro mtodo que incluya ndices para indicar los trozos de subvectores sobre los que se trabaja. Indicad qu llamada se hace al mtodo recursivo para resolver el problema inicial.

Problema 8.
Disead un mtodo tal que calcule el mximo de un vector no vaco de nmeros enteros. De forma similar al problema 4, implementad el mtodo que llama al que habis definido recursivamente para que se calcule el mximo de todo el vector.

Problema 9.
El algoritmo chino de multiplicacin. Disear un mtodo que multiplique dos nmeros enteros usando las siguientes equivalencias: ! 2 ! (! !"# 2), !" ! !" !"# !! = 2! = 2 ! ! !"# 2 + ! , !" ! !" !"#$% 2

Problema 10.

Dado un vector de nmeros enteros ordenado decrecientemente, disead un mtodo tal que compruebe si el valor de alguno de los elementos del vector coincide con su ndice. Podis hacer dos versiones: una que vaya comprobando elemento a elemento si dicha propiedad se cumple (para esta versin, el mtodo recursivo usar, adems del vector, un ndice). otra que, usando dos ndices, sea capaz de descartar a cada llamada la mitad del vector.

En ambos casos implementad los mtodos que hacen la llamada inicial al que habis diseado recursivamente dando valores iniciales a los ndices. Pista: podis pensar qu relacin tiene este problema con la bsqueda dicotmica y, si la encontris, obtendris la solucin.

Problema 11.

Un problema parecido al anterior se puede plantear cuando el vector de enteros est ordenado crecientemente y no contiene valores repetidos. El razonamiento en este caso es ms complicado que en el caso anterior (obviamente cuando se intenta hacer la versin que, a cada paso divide la longitud del intervalo donde buscar por la mitad). Pista: la idea de la solucin consiste en darse cuenta de que los valores crecen como mnimo tanto como los ndices. Esto es cierto porque el vector no contiene elementos repetidos.

Problema 12.

La sucesin de Fibonacci viene definida por la siguiente recurrencia: !!!! = !! + !!!! con valores iniciales !! = 0 y !! = 1. Disead e implementad un mtodo recursivo para calcular el ensimo trmino de la sucesin y mostrad el rbol de llamadas que se produce al calcular !! con vuestra solucin.