Project Euler #44: A Recursive Golang Solution - Part One

_________________________

few weeks ago, I started the Udemy Go (Golang) class taught by Professor McLeod. He knows his stuff and at roughly a quarter of the way through, he suggested that we pick a problem at Project Euler and build a Golang solution for it. I randomly chose Project Euler #44 - Pentagonal Numbers. A nested for-loop approach, in Go or any other language, would probably work. Then I got a bright idea: maybe I could build a strictly recursive Golang solution instead. Obviously, we should not rely on recursion as a first choice to solve problems. It has a large resource overhead and expense. A recursive solution can become tricky to build, and it can easily blow the stack. However, I wanted to push both myself and the Golang product. I built the solution with Go 1.7.4 and Webstorm 2016.3 on a Windows 7 PC. See the solution here at GitHub.

For Project Euler #44, we have to find two pentagonal numbers that together, obey three rules:

        The sum of the numbers must form a pentagonal number

        The subtracted value (larger number - smaller number) must
        form a pentagonal number

        The absolute value of the subtracted numbers must be
        minimized

The first two rules made perfect sense but I wondered about the third rule. Maybe a later pair of larger numbers might have a smaller distance between them. Then I looked at the pentagonal number

p_n = \tfrac{3n^2-n}{2}

equation. If we start the search from this number pair

        P1 = 1
and

        P2 = 5

as known pentagonal numbers, I decided that since the equation has a monotonic increasing derivative

p_n = \tfrac{3n^2-n}{2}

for n > 0, the first number pair

        (P0, P1)

that satisfies all the rules would solve the problem.

Based on the P
n equation above, the integers "n" map to pentagonal numbers like so:

        n pentagonal number (P
n)
      ____________________________

        1          1
        2          5
        3        12
        4        22
        5        35
        6        51
        7        70
        8        92
        9      117
       10     145
        .          .
        .          .
        .          .


To solve the problem, we can start with a pair of integers

        (P0, P1)

as shown in the table. Pseudo-code for search would look like this:

        (outer loop)

              increment P1 by one
              set Pto (P1 - 1)

              (inner nested loop)

                    with P1 fixed, decrement Pby one until we hit P0 = 1
                    at each decrement of P0, test the (P0, P1) pair against
                          the rules

Inside the inner loop, each time P0 decrements, map the (P0, P1) pair into pentagonal numbers. IP0  hits 1 and the (P0, P1) pair did not satisfy the listed conditions, then leave the inner loop, run the outer loop once

        increment P1 by one
        set P0  to (P1 - 1)

and proceed. When the integer pair satisfies the conditions

        P1 is a pentagonal number
        P0 is a pentagonal number
        (P1 + P0) is a pentagonal number
        (P1 - P0) is a pentagonal number

we solved the problem. The Project Euler folks probably expected a nested loop solution. I had other ideas as we'll see in Part Two.

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

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

        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, 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

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