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 think of 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 structures, 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
main()
function, 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. Note how these type declarations operate. These declarations specify the types of the parameters that the function signatures expect. Golang expects variable names to the left of the variable types. Line 38 shows this. It 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 line declaration, 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]. Then, they test the sum and difference values of these calculated pentagonal numbers with the
is_pentnum()
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, x[0] and x[1], as a pair 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 determine 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 map 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]
pair 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]
pair values that solve the problem. For some reason, Golang wants 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 adds one to the x[1] value, 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. This works just like line 38 as described above. The
outer_is_sum_pentnum
and
inner_is_sum_pentnum
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. It has a structure that matches the signature of the innerfuncvar declaration of line 36, substituting variable names in the call to the to the inner_recfunc anonymous function. 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
x[1]++
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 map to the outer loop of a nested for-loop solution. The call operates like line 104 as described above. 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.
Certainly for Golang, and possibly for other language products that offer recursion, anonymous functions, and pointers, the software featured in this article shows that a nested recursion solution would involve three factors:
Taken together, the three factors listed here together offer a powerful way to lever the true potential of recursion, to solve problems that loop solutions might not handle.
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 think of 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 structures, 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
main()
function, 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. Note how these type declarations operate. These declarations specify the types of the parameters that the function signatures expect. Golang expects variable names to the left of the variable types. Line 38 shows this. It 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 line declaration, 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]. Then, they test the sum and difference values of these calculated pentagonal numbers with the
is_pentnum()
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, x[0] and x[1], as a pair 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 determine 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 map 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]
pair 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]
pair values that solve the problem. For some reason, Golang wants 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 adds one to the x[1] value, 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. This works just like line 38 as described above. The
outer_is_sum_pentnum
and
inner_is_sum_pentnum
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. It has a structure that matches the signature of the innerfuncvar declaration of line 36, substituting variable names in the call to the to the inner_recfunc anonymous function. 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
x[1]++
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 map to the outer loop of a nested for-loop solution. The call operates like line 104 as described above. 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.
Certainly for Golang, and possibly for other language products that offer recursion, anonymous functions, and pointers, the software featured in this article shows that a nested recursion solution would involve three factors:
- Recursive function variable type definitions
- Variable declarations that use the new types, and that assign recursive function code to those variables as variable values
- Use of those function-type variables. This involves appropriate argument values in the function variable signatures. It also involves "catching" all values the anonymous functions return. In effect, this factor calls the recursive functions in the right place, at the right time, with the correct arguments, in a dynamic, flexible way
Taken together, the three factors listed here together offer a powerful way to lever the true potential of recursion, to solve problems that loop solutions might not handle.
____________
_______________________
____________
After I got this software working, I modified it, to see if it would calculate other solution pairs. Unfortunately, the modified version crashed after it found the first solution pair, because the stack exploded. I found a loop solution for the problem, and I modified it to calculate the first ten solution pairs for Project Euler #44. See that loop solution here at GitHub. Although I expected the solutions to increase in distance, they behave in a random way. Sometimes they increase, and sometimes they decrease. Some deeper behavior which I don't understand probably causes this.
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 for available hardware resources, Golang recursion has flexibility and reliability.
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 for available hardware resources, Golang recursion has flexibility and reliability.