I know there is a formula for n-th even triangle, but it's just a matter of interest for me to try to write a recursive algorithm.
def even_triangle(n):
value = n * (n + 1) // 2
if value % 2 == 0:
return value
return even_triangle(n + 1)
for i in range(1, 12):
print(f"{i})", even_triangle(i))
I tried to write a function which could compute the n-th even triangle number (OEIS A014494), but it turned out that it returns the previous result if the n-th triangle number is odd, but not the next even triangle number as expected.
Output:
1) 6
2) 6
3) 6
4) 10
5) 28
6) 28
7) 28
8) 36
9) 66
10) 66
11) 66
What I expect:
1) 6
2) 10
3) 28
4) 36
5) 66
6) 78
7) 120
8) 136
9) 190
10) 210
11) 276
The reason you get duplicates follows from your recursive call:
return even_triangle(n + 1)
When this gets executed, then consequently even_triangle(n) === even_triangle(n + 1)
, which is not what you ever want to have (since it enforces the duplicate value).
When using recursion, you would typically make a recursive call on a simpler version of the problem (so with a lesser value of n
) and then "upgrade" that result with some manipulation to make it suitable for the current value of n
.
In this particular case we can see that results come in pairs of standard triangular numbers, then skipping two triangular numbers, and then again a pair, ...etc. That makes me look at a solution where you determine whether the n-th even triangular number is the first one of such a pair, or the second one. If it is the second one, the difference with the preceding n-th even triangular number (got from recursion) is the distance between normal triangular numbers, otherwise the distance is greater.
In short, we can find this recursive relation:
def even_triangle(n):
if n == 0:
return 0
elif n % 2 == 0:
return even_triangle(n - 1) + 2 * n
else:
return even_triangle(n - 1) + 6 * n
As the difference between the two recursive calls is just the factor 2 versus 6, you could produce that factor from n % 2
(i.e. 2 + (n % 2) * 4
) and merge those two recursive return
statements. The base case can also be merged into it with an and
operator:
def even_triangle(n):
return n and even_triangle(n - 1) + (2 + (n % 2) * 4) * n
As you have already noted yourself, there is a closed formula for this, so using recursion is not the most efficient here.