Ejercicio de recursividad java.

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Nos han enviado un ejercicio con recursividad en la función, que vaya tela... Me he reventado los sexos y nada, no consigo casarlo T-T.

Os pido un poco de ayuda a ver si me podéis ayudar a sacarlo.

El ejercicio dice:

Realiza una función recursiva que encuentre el primer valor N para el que la suma 1 + 2 + 3 + ... + N exceda a un valor M que se introduce por parámetro. Es decir, si M vale:
1: devuelve 2
3: devuelve 3
7: devuelve 4
10: devuelve 5

15: devuelve 6

Se puede utilizar más de un parámetro en la función, pero eso sí, debe ser recursiva... Por desgracia. Lo tengo que hacer en java (estamos usando java 12).

Gracias por la ayuda, a ver si me podéis guiar.
 

Rugamba

Master Chapuzas
Registrado
7 Ene 2014
Mensajes
1.453
Puntos
83
Edad
32
Al principio habia entendido el encuciado como el tipico algoritmo para sacar fibonachi.

Si no lo he entendido mal, la función sería algo asi:
Código:
int acumulado=0
int N=0
funcionrecursiva(int M){
    acumulado=acumulado+(N+1)
    si(acumulado>M){
        N++
        return N
    }sino{
        N++
        return funcionrecursiva(M)
    }
}
En plan rápido, tendrás que adaptarlo al lenguaje.
 
Última edición:

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Quizás no la he adaptado bien a Java, pero me da error cuando la ejecuto.

Esta es la función que he hecho:

Código:
package recursion;

public class Prueba {

    public static void main(String[] args) {

        System.out.println(recursived(6));
    }

    // Recursividad de los cojones
    public static int recursived(int m) {
        int 
        acumulado = 0,
        n = 0;
        
        acumulado = acumulado + (n+1);
        
        if (acumulado > m) {
            n++;

        } else {
            n++;
            recursived(m);
        }
        return n;
    }
}
Explico un poco mejor el ejercicio, por si ayuda en algo:

digamos que a mí me introducen el número 6 (m) en la función, pues entonces tengo que devolver el número (n) cuya suma con los anteriores supere a ese m.

Es decir, en el caso de que introduzcan un 6 en mi función, deberá devolver un 4, tal que:
1 + 2 + 3 + 4 = 10. 10 es mayor a 6 y el 10 se consigue con la suma de 4 y sus números anteriores.

Gracias por la ayuda!
 

Rugamba

Master Chapuzas
Registrado
7 Ene 2014
Mensajes
1.453
Puntos
83
Edad
32
Quizás no la he adaptado bien a Java, pero me da error cuando la ejecuto.

Esta es la función que he hecho:

Código:
package recursion;

public class Prueba {

    public static void main(String[] args) {

        System.out.println(recursived(6));
    }

    // Recursividad de los cojones
    public static int recursived(int m) {
        int 
        acumulado = 0,
        n = 0;
        
        acumulado = acumulado + (n+1);
        
        if (acumulado > m) {
            n++;

        } else {
            n++;
            recursived(m);
        }
        return n;
    }
}
Explico un poco mejor el ejercicio, por si ayuda en algo:

digamos que a mí me introducen el número 6 (m) en la función, pues entonces tengo que devolver el número (n) cuya suma con los anteriores supere a ese m.

Es decir, en el caso de que introduzcan un 6 en mi función, deberá devolver un 4, tal que:
1 + 2 + 3 + 4 = 10. 10 es mayor a 6 y el 10 se consigue con la suma de 4 y sus números anteriores.

Gracias por la ayuda!
Que error te da? es que no tengo instalado ningún IDE y no lo puedo probar.

Te comento un par de cosas:
- Te faltaría un return en el "else" --> "return recursived(m)"
- Podrias usar el siguiente codigo para que el programa te pregunte por el numero en vez de tener que introducirlo en el codigo:
Código:
import java.util.Scanner;

.
.
[COLOR=#000000][FONT=Consolas][COLOR=#0000ff]public[/COLOR][COLOR=#0000ff]static[/COLOR][COLOR=#0000ff]void[/COLOR][COLOR=#000000] main(String[] args) {[/COLOR]
[COLOR=#000000]    Scanner sc = [/COLOR][COLOR=#0000ff]new[/COLOR][COLOR=#000000] Scanner(System.in);[/COLOR]
[COLOR=#000000]    System.out.print([/COLOR][COLOR=#a31515]"Introduce el número: "[/COLOR][COLOR=#000000]);[/COLOR]
   [COLOR=#0000ff]int[/COLOR][COLOR=#000000] m = sc.nextInt();[/COLOR]
[COLOR=#000000]    sc.close();[/COLOR]
[COLOR=#000000]    System.out.print(recursived(m));[/COLOR]
[COLOR=#000000]  }[/COLOR]

[/FONT][/COLOR]
- Otra cosa, si declaras las variables (acumulado y n) dentro de la propia función, cada vez que la vuelvas a ejecutar los vuelve a igualar a cero, por lo que eso no funcionará, declaralas fuera de la funcion.
Voy a revisarlo a ver si descubro que te puede fallar.
 
Última edición:

josejfernandez

Software Architect
Registrado
1 Ago 2012
Mensajes
438
Puntos
43
La recursividad es uno de los estilos de programación básicos. Tu problema es que aún no sabes pensar de forma recursiva :p tienes que aprender a hacerlo.

Este ejercicio te ayudará a ello, pero tienes que resolverlo tú. Algo en tu cabeza tiene que hacer "click" después de pensarlo durante el tiempo que necesites, y entonces comprenderás la forma de pensar recursiva y este problema te parecerá ridículamente fácil.

Por eso considero un error darte la solución. Échale un ojo a estos textos (son dos apartados del mismo artículo):

Recursion (ciencias de computacion) - Wikipedia, la enciclopedia libre
Recursion (ciencias de computacion) - Wikipedia, la enciclopedia libre
 

Rugamba

Master Chapuzas
Registrado
7 Ene 2014
Mensajes
1.453
Puntos
83
Edad
32
La recursividad es uno de los estilos de programación básicos. Tu problema es que aún no sabes pensar de forma recursiva :p tienes que aprender a hacerlo.

Este ejercicio te ayudará a ello, pero tienes que resolverlo tú. Algo en tu cabeza tiene que hacer "click" después de pensarlo durante el tiempo que necesites, y entonces comprenderás la forma de pensar recursiva y este problema te parecerá ridículamente fácil.

Por eso considero un error darte la solución. Échale un ojo a estos textos (son dos apartados del mismo artículo):

Recursion (ciencias de computacion) - Wikipedia, la enciclopedia libre
Recursion (ciencias de computacion) - Wikipedia, la enciclopedia libre
Muy cierto, le he dado una respuesta rapida en pseudocodigo porque sé que ya lleva un tiempo mirando temas de programación, aunque igual aun no habia mirado la recursividad jeje. Saito_25 asegurate de entender bien lo que "estamos" haciendo aquí y pregunta cualquier duda ;) ¿has podido probar lo que te he comentado antes?
 

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Buenas,

De nuevo, gracias a ambos.

Es cierto que me está costando muchÃ*simo el tema de la recursividad porque no consigo entender qué devuelve cada función o cómo utilizarla.

No es que no haya leÃ*do sobre la recursividad, pero todavÃ*a necesito ese "click". Seguramente sea más fácil de lo que mi cabeza me hace ver.
Rugamba, el error que me da es de overflow, es decir, el programa no termina nunca de ejecutarse. He probado también con el return que me has dicho, pero da el mismo error.

Se ha resuelto en clases la actividad, aunque el resultado final me parece excesivamente feo... Creo que este ejercicio no está pensado para hacerse con recursividad, pero bueno, me gustarÃ*a mejorarlo un poco más a poder ser.

Por si ayuda a comprender lo que quiero mejorar, os pongo el código "resuelt".

Código:
package recursion;

public class Ejercicio3 {

    public static void main(String[] args) {

        // VARIABLES
        
        // EJERCICIO 3
        System.out.println(maximum(6, 0, 0));
    }

    // Devolver un n cuya suma sea mayor a un m
    public static int maximum(int m, int i, int cont) {
        
        int result;
        
        if (cont > m) {
            result = i;
        } else {
            i ++;
            result = maximum(m, i, cont+i);
        }
        
        return result;
    }
}
 

josejfernandez

Software Architect
Registrado
1 Ago 2012
Mensajes
438
Puntos
43
Parece una solución correcta. La clave la tenías en el enunciado: "se puede utilizar más de un parámetro en la función". Que la función tenga dentro de ella los datos es un error; debe recibirlos de fuera. Dices que te parece feo, en otros lenguajes puedes solucionarlo con los parámetros con valor predeterminado, es decir:

Código:
int maximum(int m, int i = 0, int cont = 0)
Y a la hora de llamarla inicialmente:

Código:
Console.WriteLine(maximum(6));
Pero bueno, eso ya son particularidades del lenguaje. Dos apuntes que sí quiero hacer:

el error que me da es de overflow
Eso no es que el programa "no termine nunca", sino que estás llenando la pila de llamadas. Cuando llamas a una función, esa llamada se almacena en esa pila de llamadas para que al retornar de dicha función la ejecución continúe en el punto donde se abandonó. Tiene un tamaño limitado que depende del lenguaje que estés usando.

La recursividad es una forma de solucionar problemas que es muy stack-intensive. Es decir, utiliza mucho esta pila de llamadas. Tu problema de stack overflow es básico: no has controlado correctamente la recursividad, y ésta no para de llamar, y llamar, y llamar... No retorna nunca, ergo la pila se llena.

este ejercicio no esta pensado para hacerse con recursividad
Puedes no verle ventajas ahora mismo, y en este caso es verdad que resolver el problema de este modo parece algo poco natural. En cambio, existen multitud de problemas que se resuelven de forma ridículamente fácil si se hace de forma recursiva, mientras que tienen difícil solución si se abordan de otras formas.

Lo importante ahora es que aprendas a pensar de forma recursiva. Plantéate este otro problema, que se resuelve de forma muy natural con recursividad: listar el contenido de un directorio, y de los directorios dentro de éste, y de los directorios dentro de éstos, y de los directorios dentro de éstos... Hasta mostrar todo el contenido.
 

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Gracias por la ayuda y los consejos!

Sé que la recursividad es un arma poderosa, pero también (al menos en mi caso) difícil de usar por ahora.

Tengo pendiente leer los enlaces que me has pasado, en cuantito pueda.

Me parece feo tener que usar más de un parámetro para calcular un solo valor, me refería a eso. Y por otro lado, si uso variables que están fuera de la función, la función no podría reutilizarla en otro código, ¿no? Bueno, a no ser que le vuelva a crear las mismas variables.

Y gracias por las correciones ;).
 

Rugamba

Master Chapuzas
Registrado
7 Ene 2014
Mensajes
1.453
Puntos
83
Edad
32
Era una de las cosas que te comenté, cada vez que llamabas a la función volvías a igualar las variables a 0, por eso no terminaba nunca. Me estoy dando cuenta de lo oxidado que estoy después de unos añitos sin programar nada de nada....T_T

Para mí uno de los ejercicios básicos de la recursividad es el calculo del factorial de un número. https://www.campusmvp.es/recursos/p...ad-o-recursion-Un-ejemplo-con-JavaScript.aspx Aquí el ejercicio explicado, con video de la traza. Creo que se entiende muy bien.

Como reto el ejercicio de recursividad que te propondría (si quieres seguir mirando por tu cuenta) es el calculo de la sucesión de Fibonacci, es uno de los problemas clásicos. A mí me lo explicaron y me lo hicieron hacer tanto en el ciclo cómo en las carreras, siempre cae jeje. (Sucesion de Fibonacci - Wikipedia, la enciclopedia libre)
 

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Pues sí XD, siempre cae.

Ya lo tengo hecho, tanto en bucle como en recursividad, jaja. El boletín de recursividad que nos han dado, es de 6 actividades y entra de todo... El último es la torre de hanoi... Una locura.

Vamos, he tenido que hacer el factorial, el mcd de dos números, la serie de fibonacci, darle la vuelta a una frase... Cada cual, más interesante que el otro XD.

Pues a ver si tengo algo de tiempo y me veo los enlaces que me habéis pasado, thanx!
 

josejfernandez

Software Architect
Registrado
1 Ago 2012
Mensajes
438
Puntos
43
Me parece feo tener que usar más de un parámetro para calcular un solo valor, me refería a eso.
Lo sé, pero a veces es necesario. Y para hacer la función reutilizable de verdad, en realidad es el mejor camino. Cuantos menos números mágicos tenga un programa, mejor. Por ejemplo, una función para calcular la edad de una persona, puede recibir la fecha de nacimiento y la fecha actual, en lugar de obtener la fecha actual por si misma. Esto te permite reutilizarla para más casos que el planteado inicialmente. Y además, permite testearla mejor.

Los ejemplos que ponéis (factorial, Fibonacci) son los típicos, pero no por ello los que mejor se adaptan a la recursividad. Con ellos el cerebro te pide hacerlo de forma lineal (con bucles), y de hecho de esa forma el programa rendirá mejor (las llamadas a función tienen un coste, elevado en la mayoría de lenguajes).

En cambio, el ejemplo que os planteo (listar todos los contenidos de un directorio) es un problema que el cuerpo te pide resolver de forma recursiva. De hecho, buena suerte haciéndolo de forma no recursiva :eek:k:

Que te estén enseñando recursividad y que te hagan enfrentarte a problemas como la Torre de Hanoi habla bien de tu programa formativo, en mi opinión (estoy asumiendo que es un ciclo formativo).
 

Rugamba

Master Chapuzas
Registrado
7 Ene 2014
Mensajes
1.453
Puntos
83
Edad
32
Lo sé, pero a veces es necesario. Y para hacer la función reutilizable de verdad, en realidad es el mejor camino. Cuantos menos números mágicos tenga un programa, mejor. Por ejemplo, una función para calcular la edad de una persona, puede recibir la fecha de nacimiento y la fecha actual, en lugar de obtener la fecha actual por si misma. Esto te permite reutilizarla para más casos que el planteado inicialmente. Y además, permite testearla mejor.

Los ejemplos que ponéis (factorial, Fibonacci) son los típicos, pero no por ello los que mejor se adaptan a la recursividad. Con ellos el cerebro te pide hacerlo de forma lineal (con bucles), y de hecho de esa forma el programa rendirá mejor (las llamadas a función tienen un coste, elevado en la mayoría de lenguajes).

En cambio, el ejemplo que os planteo (listar todos los contenidos de un directorio) es un problema que el cuerpo te pide resolver de forma recursiva. De hecho, buena suerte haciéndolo de forma no recursiva :eek:k:

Que te estén enseñando recursividad y que te hagan enfrentarte a problemas como la Torre de Hanoi habla bien de tu programa formativo, en mi opinión (estoy asumiendo que es un ciclo formativo).
Muy de acuerdo. Yo hice ciclo y carrera y ni en el ciclo ni en las 3 primeras asignaturas de programación se habla de costes y realmente creo que se debería tratar de lo primero ya que es lo que te puede hacer decidir que tipo de algoritmos utilizar a la hora de afrontar un problema. Está claro que primero se deben conocer los tipos de algoritmo ya que no se te va a ocurrir usar un arbol vl si no sabes lo que es, pero me parece muy interesante saber como calcular costes de ejecución.

Tanto las torres de hanoi como fibonacci a mi me ha tocado hacerlo en todas las asignaturas de programación en todos los lenguajes que me han enseñado.
Saito_25 mucho animo y aquí estamos para ayudarte a entender lo que sea, así de paso voy desempolvando mi estantería cerebral donde guardo todo lo de programación :D
 

josejfernandez

Software Architect
Registrado
1 Ago 2012
Mensajes
438
Puntos
43
Yo hice ciclo y carrera y ni en el ciclo ni en las 3 primeras asignaturas de programación se habla de costes y realmente creo que se debería tratar de lo primero ya que es lo que te puede hacer decidir que tipo de algoritmos utilizar a la hora de afrontar un problema. Está claro que primero se deben conocer los tipos de algoritmo ya que no se te va a ocurrir usar un arbol vl si no sabes lo que es, pero me parece muy interesante saber como calcular costes de ejecución.
No sé si es de lo primero que debería aprenderse, pero debería aprenderse. Siempre. Por lo menos lo básico, como Big O y aplicarlo a estructuras de datos y/o algoritmos. Como siempre, las ecuaciones y el trasfondo matemático que hay detrás ya si eso lo dejamos para los matemáticos. Opino que no es necesario. En mi caso, ni idea de esos cálculos y ecuaciones.
 

Megaman

Master Chapuzas
Registrado
19 Sep 2019
Mensajes
803
Puntos
43
Yo no lo resolvería nunca con una función recursiva, pero con un pequeño truco puede hacerse:

public int getN(int M) {
return getN(M,1);
}

private int getN(int M, int inicio) {
//al lío
int suma = 0;

for (int i=0; i<inicio; i++) {
suma+=i;
}
if (suma> M) {
return inicio;
} else {
return getN(M, inicio+1);
}
}
 
Última edición:

Saito_25

Personal vaguer
Registrado
15 Mar 2015
Mensajes
910
Puntos
43
Así a priori no entiendo qué hace el código, voy a tener que analizarlo.

De todos modos, no podemos usar búcles para resolver el ejercicio, la cuestión es que nos friamos la cabeza haciéndolo solo con recursividad XD.

Pues el último que me quedaba, que era las torres de hanoi lo he programado en 2 minutos XD... Y ni sé cómo.

Gracias a todos por la ayuda y por el ofrecimiento de Rugamba, si se me plantea otra duda, espero poder contar con vosotros ;).

Por cierto, me leí los temas (que estaban en español los que están en inglés los estoy intentando leer) y me han ayudado bastante a comprender la recursividad.

PD: el juego no conseguí terminarlo, Rugamba, pero lo tengo en mente para un futuro no muy lejano.
 

Megaman

Master Chapuzas
Registrado
19 Sep 2019
Mensajes
803
Puntos
43
Así a priori no entiendo qué hace el código, voy a tener que analizarlo.

De todos modos, no podemos usar búcles para resolver el ejercicio, la cuestión es que nos friamos la cabeza haciéndolo solo con recursividad XD.

Pues el último que me quedaba, que era las torres de hanoi lo he programado en 2 minutos XD... Y ni sé cómo.

Gracias a todos por la ayuda y por el ofrecimiento de @Rugamba, si se me plantea otra duda, espero poder contar con vosotros ;).

Por cierto, me leí los temas (que estaban en español los que están en inglés los estoy intentando leer) y me han ayudado bastante a comprender la recursividad.

PD: el juego no conseguí terminarlo, Rugamba, pero lo tengo en mente para un futuro no muy lejano.
Hombre podríamos usar una función para calcular la suma 1,2,3...n de forma recursiva


Lo que hago en mi código anterior es usar la sobrecarga de métodos (familiarizate con ello porque es importante). Mi código completo quedaría así:


public int getN(int M) {
return getN(M,1);
}

private int getN(int M, int inicio) {
if (sumaRecursiva(inicio)> M) {
return inicio;
} else {
return getN(M, inicio+1);
}
}

private int sumaRecursiva(int n) {
if (n==1) {
return n;
} else {
return n+sumaRecursiva(n-1);
}

Si no entiendes algo puedes preguntarme lo que quieras
 
Última edición:

NikoUcra

Chapuzas Jr
Registrado
10 Dic 2016
Mensajes
21
Puntos
0
Edad
21
Solución Recursividad

Buenas, aquí ando en clase de Sistemas Inteligentes.
He creado dos clases, la del Main y la clase donde está el algoritmo.
Main:
public class JavaApplication4 {


/**
* @param args the command line arguments
*/
public static void main(String[] args) {
clase objeto=new clase();
System.out.println("La solución es: "+objeto.EncuentraIncognitaRecursivo(15));

}

}
Algoritmo:
public class clase {


int M;
int acumulada;


public clase() {
this.M = 0;
this.acumulada = 0;
}


public int EncuentraIncognitaRecursivo(int incognita) {
int solucion = 0;
acumulada = acumulada + M;
if (acumulada > incognita) {
solucion = M;
} else {
M++;
solucion = EncuentraIncognitaRecursivo(incognita);
}


return solucion;
}
}
 

josejfernandez

Software Architect
Registrado
1 Ago 2012
Mensajes
438
Puntos
43
He creado dos clases, la del Main y la clase donde está el algoritmo.

(...)

Algoritmo:
public class clase {


int M;
int acumulada;


public clase() {
this.M = 0;
this.acumulada = 0;
}



(...)
}
}
Tu propuesta es una mala práctica. La clase que propones tiene estado interno. En este problema ni es necesario, ni tampoco es recomendable: lo suyo es tender hacia los objetos inmutables siempre que sea posible. Y en este caso lo es. Es mejor solución la de @Megaman con sobrecarga, o mismamente la que se ha dado como resuelta en el curso de @Saito_25.
 

Megaman

Master Chapuzas
Registrado
19 Sep 2019
Mensajes
803
Puntos
43
Tu propuesta es una mala práctica. La clase que propones tiene estado interno. En este problema ni es necesario, ni tampoco es recomendable: lo suyo es tender hacia los objetos inmutables siempre que sea posible. Y en este caso lo es. Es mejor solución la de @Megaman con sobrecarga, o mismamente la que se ha dado como resuelta en el curso de @Saito_25.
Es cierto...cada vez que quieras usarla tienes que instanciarla, creando un objeto del cual sólo puedes invocar el método una vez, porque los atributos M y acumulada quedan modificados. A no ser que hagas la chapuza de volver a ponerlos a cero entre invocación e invocación bien haciéndolos públicos o bien mediante un setter. Sin embargo mis métodos pueden incluirse en una clase y hacerse incluso estático el público, de modo que no haya que instanciar ningún objeto ni nada.
 
Arriba