Project Euler #44: a recursive Golang solution - Part Two


In Part One, I described Project Euler #44 and an overall way to solve it. Here in Part Two, I will describe a recursive Golang solution for this problem. See that solution  at GitHub.

In an earlier article, I wrote a detailed explanation of recursion in a SQL Server 2005+ context. We can generally describe software that calls itself in a controlled way as recursive. Recursion involves a lot more than that, of course, but this description will work for now. A software system that repeatedly calls itself until a defined "base case" occurs means that we can substitute recursive code for a loop, because in a conventional loop, the code repeats a finite number of times. In Part One, we saw that a conventional Project Euler #44 solution would probably have two nested for-loops. Therefore, I figured that maybe I could nest two recursive elements, one to primarily handle P0 and one to primarily handle P1. As we'll see, this worked.

In the Golang solution, function

        func gen_pentnum(n int) int {

at line 9 takes integer parameter n and returns a pentagonal number. At line 18, the function

        is_pentnum(n int) bool

takes integer parameter n and tests whether or not n is a pentagonal number, returning a boolean value.

In the


lines 35 and 36 first declare

      type outer_recfunc func(outer_recfunc, []int) []int
        type inner_recfunc func(inner_recfunc, []int) bool

as user-defined function types. Note that the first parameter of each type is the type itself, and this makes the recursion possible. Both functions also take an integer array as their second parameter. Line 38 declares variable innerfuncvar

        innerfuncvar := func(move_x0_variable inner_recfunc, x []int) bool {

and assigns an anonymous function of type inner_recfunc to it. Matching the declaration of line 36, this anonymous function has two parameters. The first parameter (move_x0_variable) has type inner_recfunc. The second parameter (x) has an integer array type. This array will hold the

        x[0] x[1]

values which map to the

        (P0, P1)

values described in Part One. Lines 48 and 49

  inner_is_sum_pentnum := is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]))
  inner_is_diff_pentnum := is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]))

calculate pentagonal numbers for x[0] and x[1], and then test the sum and difference values of these calculated pentagonal numbers with the


function. Line 51

        if !(inner_is_sum_pentnum && inner_is_diff_pentnum) {

uses the values from lines 48 and 49 in an if - else structure. In its first if-block, both x[0] and x[1] don't solve the problem. Note that here in innerfuncvar, x[1] stays fixed. We only want to move x[0] down towards 1. Therefore, at line 52, we'll first see if we even have room to do this. If we do, decrement x[0] at line 61, and then recursively call innerfuncvar

        return move_x0_variable(move_x0_variable, x)

with a return, because the function must return a value. This recursive call would correspond to the inner loop of a nested for-loop solution. Note that the declarations at lines 35 and 36 expect an integer array as the second argument / parameter. Since we named the array variable "x", we can simply use "x" in these recursive calls. In the else-block at line 63, x[0] hit 1, but the sum and difference do not map to pentagonal numbers. We can't move x[0] to an integer value less than 1. Therefore, at line 74, innerfuncval returns false for this code block because we did not find the

        x[0] x[1]

values that solve the problem.

In the line 76 then-block, innerfuncvar() found the x[0] and x[1] values that satisfy all conditions

        1) x[1] maps to a pentagonal number
        2) x[0] maps to a pentagonal number
        3) (x[1] + x[0]) maps to a pentagonal number
        4) (x[1] - x[0]) maps to a pentagonal number

and at line 87, this then-block returns a boolean true. The x[] array is essentially a pointer, and the innerfuncvar() anonymous function can change values in the x[] array because the function operates on the array values through the x[] pointer value. The function "sees" that pointer value as the x[] array syntax. Therefore, the innerfuncvar variable won't need to physically return the x[] array. It will only need to return a boolean, which tells its caller whether or not it found the

        x[0] x[1]

values that solve the problem. For some reason, Golang expects to see a return value as the last line of a recursive anonymous function, outside of any / all if-then blocks. After some research and experimentation, I discovered that

        return true
as a returned boolean value at line 89 will work.

Variable outerfuncvar at line 92 works a lot like innerfuncvar of line 38. The outerfuncvar anonymous function primarily moves the x[1] value out, resets x[0] when needed, and recursively calls itself. This recursive function would work like the outer loop of a nested for-loop solution. It returns integer array x when innerfuncvar finds the

        x[0] x[1]

values that solve the problem. At line 92, the main() function declares variable outerfuncvar

        outerfuncvar := func(move_x1_variable outer_recfunc, x []int) []int {

and assigns an anonymous function of type outer_recfunc to it. The




variables of lines 94 and 95 work similar to the variables of lines 48 and 49. Line 97

        if !(outer_is_sum_pentnum && outer_is_diff_pentnum) {

tests if the

        x[0] x[1]

values solve the problem. If they don't, line 102

        x[0] = x[1] - 1

resets x[0] to just before x[1]. Line 104

        if !innerfuncvar(innerfuncvar, x) {

calls innerfuncvar. Even though this call happens outside innerfuncvar, the syntax here still looks like a recursive call. Because innerfuncvar returns a boolean, it tells outerfuncvar whether or not it found the

        x[0] x[1]

values that solve the problem. In the first if-block, it did not. Therefore, lines 124

        x[0] = x[1]

and 125


formally reset x[0] and x[1], and line 127

        return move_x1_variable(move_x1_variable, x)

recursively calls the "outer" recursive function move_x1_variable. This recursive call would correspond to the outer loop of a nested for-loop solution. If line 97 sees that the

        x[0] x[1]

values solve the problem, lines 134 and 138 return array x, similar to the way lines 87 and 89 of innerfuncvar work.

In main(), line 147

        a := []int{1, 5}

formally declares an integer array, loading it with the first two known pentagonal numbers. Line 157

        countarray := outerfuncvar(outerfuncvar, a)

launches everything. The rest of main() outputs the solution, with some extra metadata, to the console.

The recursion described here became tricky because I had to find and account for all the various cases and conditions inside the anonymous recursive functions. However, for some problems recursion offers the only feasible solution, and this Project Euler #44 solution shows that Golang recursion has flexibility and reliability.