Triangle numbers & Recursion Concept

Triangle numbers follow the principle :- The nth number in a series is obtained by adding n to the previous term.

First number ==> 1
Second number ==> previous number which is 1 + next position which is 2 = 3
Third number ==> previous numbers which is 3 + next position which is 3  = 6
Fourth number ==> previous numbers which is 6 + next position which is 4  = 10

..... and this continue .

So the triangle number series ==> 1,3,6,10,15,21,28......

There is one more way to find triangle numbers pictorially.

*
* *
* * *
* * * *
* * * * *
5 4 3 2 1  --> Position

From the above star triangle we can calculate the triangle number.

At first position number of star is 1
At second position, number of stars are 3
At third position, number of stars are 6
At fourth position, number of stars are 10
At fifth position, number of stars are 15

So using the above logic we can write a program to calculate triangular number such that nth position is the sum of n-1,n-2,n-3....n-n


There are two ways we can implement this algorithm:-

First Option:-

public static int triangleNumber(int position){

int total=0;

while(position>0){

total = total +position;

position--;

}

return total;

}

Second Option:-

We can achieve this through recursion. Recursion is a technique where a method call itself again & again till it reached a base case. Point to be noted is that if there is no base case in the recursion method call , than it will keep iterating infinitely. So it is important to have a base case.

public static int triangleNumberWithRecursion(int position)

{

if(position==1)

return 1;

else

return( position + triangleNumberWithRecursion(position-1) );

}

Mathematical Formula to get Triangle number --> nth triangular number = (n2+n)/2

Recursion Efficiency :-

There is some overhead involved when a method call itself. Recursion basically saves all the calls and arguments passed onto a stack in internal memory. Incase of large data, this can lead to stack overflow exception.

Recursion is a concept which simplifies the problem, but there is a trade off in terms of memory management and therefore, efficiency.