Bead Diagram

It takes a little thought (or a diagram) to work this out. The bead diagram shows how the recursion works. The method is first called using:

sum( 1, 5 )

which calls

sum( 2, 5 )

and so on until the base case is reached. The base case is represented by the last circle in the diagram.

sum( 5, 5 )

Then the sums are computed (and tasks are completed starting at the last circle and going upward) until the final sum is performed and the work is finished.

The operation of this method is very close to that of the method for triangle numbers.