0

estoy haciendo ejercicios de recursividad en java y me he topado con este: "En un triángulo de Pascal, como se puede observar en el ejemplo de la siguiente figura, cada elemento es la suma de los dos elementos situados sobre él, excepto el primero y último de cada fila que valen 1.
introducir la descripción de la imagen aquí


Escribir un método de clase recursivo que devuelva el i-ésimo elemento de la fila f de un triángulo de Pascal; su cabecera será entonces del tipo public static int trianguloPascal(int f, int i)."

Mi código es el siguiente:

public static int trianguloPascal(int f, int i){
  if(f == 1){
    return 1;
  }else{
    trianguloPascal(f - 1, i);
    
  }
}

Lo que trato de hacer es llegar al caso base que es cuando f vale 1 y devolver el valor del elemento de esa fila, en este caso 1. Pero no sé cómo calcular los elementos de las filas restantes.

4
  • Bienvenido a StackOverflow en español. Sería excelente si pudieras adjuntar un ejemplo mínimo verificable del código en la pregunta. Para familiarizarte con el sitio, puedes leer "Cómo preguntar" y hacer el recorrido de bienvenida para entender cómo funciona. Commented el 17 feb. 2022 a las 10:12
  • Vale, ya está. No lo había puesto porque es muy cortito y pensaba que no era relevante ponerlo. Gracias por mandarme los enlaces.
    – Ardust
    Commented el 17 feb. 2022 a las 10:19
  • En esta pregunta (aunque está en C) ya podés ver una lógica similar a la que buscás. Es cuestión de buscar ;)
    – padaleiana
    Commented el 17 feb. 2022 a las 10:26
  • padaleiana el ejemplo que citas es una solución iterativa sobre el problema, no recursiva. Al menos yo, no encontré ninguna referencia en SO en español sobre este úlitmo enfoque en particular. Commented el 17 feb. 2022 a las 11:01

1 respuesta 1

1

Como usualmente sucede en los problemas de recursividad, muchas veces el mayor desafío es encontrar las condiciones correctas de corte.

Condición de corte

En nuestro caso sabemos que la recursividad se detendrá (devolver 1, los casos triviales) bajo tres condiciones (pueden ir juntas, por claridad las he separado)

  • Cuando la fila sea la 0 (la primera) entonces evidentemente el elemento a retornar es 1.

  • Cuando en una fila dada, sea la primer columna (i == 0) entonces el elemento a retornar es 1.

  • Cuando en una fila dada, sea la última columna (i == f) entonces el elemento a retornar es 1.

Recursividad

Mirando la figura, es rápido suponer para los casos no triviales, que la definición del elemento es la suma de la i-ésima posición de la fila superior, más la i-ésima - 1, siempre. Sabemos que la "fila de arriba" se representa como f-1. Entonces la llamada recursiva sería algo así como

return trianguloPascal(f-1, i-1) + trianguloPascal(f-1, i)

Código final

public static int trianguloPascal(int f, int i){
    if(f == 0) { // Si es la fila 1, el elemento es 1
        return 1;
    }
    if(i == 0) { // Si es el primero de la fila, el elemento es 1
        return  1;
    }
    if(f == i) { // Si es el último de la fila, el elemento es 1
        return  1;
    }
    // Usando guard clauses, si llegó hasta acá es porque no es un caso trivial, toca calcular
    return trianguloPascal(f-1, i-1) + trianguloPascal(f-1, i);   
}
1
  • Muchísimas gracias, ya lo entiendo :)
    – Ardust
    Commented el 19 feb. 2022 a las 10:55

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.