pythonrecursionsequencepascals-triangleoeis

How to obtain n-th even triangle number using recursive algorithm


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

Solution

  • 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.