I'm doing recursion exercises in java and I've come across this: "In a Pascal's triangle, as can be seen in the example in the following figure, each element is the sum of the two elements above it, except the first and last of each row that are worth 1.
Write a recursive class method that returns the ith element of row f of a Pascal's triangle; its header will then be of type public static int trianguloPascal(int f, int i)."
My code is the following:
public static int trianguloPascal(int f, int i){
if(f == 1){
return 1;
}else{
trianguloPascal(f - 1, i);
}
}
What I am trying to do is get to the base case which is when f is equal to 1 and return the value of the element of that row, in this case 1. But I don't know how to calculate the elements of the remaining rows.
As is often the case with recursion problems, often the biggest challenge is finding the right cutoff conditions .
cutting condition
In our case we know that the recursion will stop (return , trivial
1
cases ) under three conditions (they can go together, for clarity I have separated them)When the row is the
0
(the first) then obviously the element to return is1
.When in a given row, it is the first column
(i == 0)
, then the element to return is1
.When in a given row, it is the last column
(i == f)
, then the element to return is1
.recursion
Looking at the figure, it is quick to assume for the non-trivial cases, that the definition of the element is the sum of the
i-ésima
position of the top row, plus thei-ésima - 1
, always. We know that the "top row" is represented asf-1
. So the recursive call would be something likeend code