Here are the two parts to recursion:
And here is how this applies to triangle numbers:
When N
is larger than 1,
the problem Triangle(N)
is divided into two
smaller problems:
Triangle(N-1)
Sometimes a smaller problem can be solved immediately (when it is the base case). Other times you need to continue breaking the problem into smaller problems.
Using the above, what is Triangle(4)
?
Fill in the boxes starting with the second column of the top row and work your way down.
When you hit the last row you can work your way up with the last two columns.