Finding the nth triangular number

Question

def triangularNumber(n):
 if(n == 1):
 return 1
 else:
 return triangularNumbers(n-1)+n

works great to find the nth triangular number up to 996... I get some error in the recursion after 996. But can tell what it is because it just keeps running through the loop. Anyone see the error?

• glampert: You are probably getting a stack overflow (the error, not the website ;))

Answer 1

Using recursion is generally advised against, as it takes longer that iterating, and can run into what you ran into, a RuntimeError: maximum recursion depth exceeded. Note you can change the maximum recursion depth, but it is generally advised against, and can lead to stack or memory overflows. In this case, you should iterate.

def triangular_number(n):
 i = n
 while True:
 if i == 1:
 return n
 i -= 1
 n += i

(This keeps running in the same function call, reducing the addition factor by one each time.)

Or better yet, use a range (or xrange for Python 2):

def triangular_number(n):
 for i in range(n): # range(3) is a generator for [0, 1, 2]
 n += i
 return n

Or better yet, use sum:

def triangular_number(n):
 return sum(range(n + 1))

Or, even better, use the formula for triangle numbers.

def triangular_number(n):
 return n * (n + 1) // 2 # Convert to int for Python 2

Answer 2

I would advice writing a more general function and then maybe defining an helper, like:

def polygonal(n, sides):
 return (n**2*(sides-2) - n*(sides-4)) // 2
def triangular(n):
 return polygonal(n, 3)

This may take a little bit more code, but will allow easier use of other n-gonals numbers.

Please note that you may do without triangular and call:

polygonal(n, sides=3)

• user61114: Also, note you can do triangular = functools.partial(polygonal, sides=3).