Part Six - An Euler 44 Nested Recursive Solution
Nested C++ Recursion - Introduction (Main Article Page)
Part Five - Stack Configuration showed how to configure the stack for the nested C++ recursion solution we'll build for the Euler 44 Pentagonal Numbers problem. Here, we'll explore an actual nested C++ recursive solution to that problem.
This C++ recursive solution available here calculates the Euler Project #44 solution with nested recursive lambdas:
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7. #include <vector>
8.
9. bool is_pentnum(int x) {
10.
11. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
12. return (((testval - trunc(testval)) == 0.0) ? true : false);
13. };
14.
15. int gen_pentnum(int n) {
16.
17. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
18. };
19.
20. int main() {
21.
22. std::function<bool (int[])> innerRecLambda;
23. innerRecLambda = [&innerRecLambda](int x[]) {
24.
25. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
26. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
27.
28. if ((x[0] > 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29.
30. x[0]--;
31.
32. return innerRecLambda(x);
33. } else if ((x[0] == 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
34.
35. return false;
36. } else {
37.
38. return true;
39. }
40. };
41.
42. std::function<int* (int[])> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
44.
45. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
46. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
47.
48. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
49.
50. x[0] = x[1] - 1;
51.
52. if (!(innerRecLambda(x))) {
53.
54. x[0] = x[1];
55. x[1]++;
56.
57. return outerRecLambda(x);
58. } else {
59.
60. return (x);
61. }
62. } else {
63.
64. return (x);
65. }
66. };
67.
68. int startValues[2] = {1, 2};
69. int* finishedValues;
70.
71. auto startTime = std::chrono::high_resolution_clock::now();
72.
73. finishedValues = outerRecLambda(startValues);
74.
75. auto endTime = std::chrono::high_resolution_clock::now();
76. std::chrono::duration timeDifference = endTime - startTime;
77.
78. std::cout << "\n\tThe calculated x vector values --> pentagonal numbers: " << "\n\n";
79. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
80. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
81. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
82. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
83.
84. std::cout << std::boolalpha;
85.
86. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0])) << "\n\n";
87. std::cout << "\t______________________________________________\n";
88. std::cout << "\t______________________________________________\n\n\n";
89. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
90. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
91. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
92. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
93. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0])) << "\n\n";
94.
95. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
96.
97. system("pause");
98.}
Download the files for this solution from this GitHub resource. Line 68 defines integer array startValues, and initializes it to the first pair of n values. Line 69 declares integer array finishedValues. This stores the n values that map to the pentagonal number solution pair. Line 71 saves the starting time, and line 75 saves the ending time. Line 73 calls outerRecLambda() and passes the startValues array as an argument. This call returns the calculated solution pair to the finishedValues array.
This solution uses two lambdas, one declared at lines 22 and 23, and one declared at lines 42 and 43. Lines 42 and 43 declare the outerRecLambda lambda:
42. std::function<int* (int[])> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
This recursive lambda mirrors the outer loop in the Euler 44 nested loop solution we saw in Part Two - Pentagonal Numbers. Lambda declarations and definitions offer many options. Here, we need to declare and define a lambda value. On line 42, the std::function keywords “wrap” the lambda code in a class that we can use to assign the lambda to a variable. In this case, we’ll assign the lambda to the variable name outerRecLambda. outerRecLambda will return a pointer to an integer, and it has an input parameter of type integer array. In the angle brackets, int* declares the data type of the lambda return value. Inside the nested parentheses, int[] declares the input parameter data type of the lambda. outerRecLambda operates as a function variable, or an anonymous function. We can easily pass arguments to anonymous functions, and receive values from them. We can also call an anonymous function recursively. This flexibility means that we can recursively call outerRecLambda, with its argument, at line 57. Finally, the declaration names the lambda outerRecLambda at line 43.
Through a closure, a function can “see” objects and variables outside of its definition. In C++, lambdas support closures, and as a result, they can “see” objects and variables outside their formal definitions. This offers even more flexibility. The lambda definition syntax places the closure values in square brackets. The lambda definition starts on line 43, and in the square brackets, the &outerRecLambda and &innerRecLambda parameters form a closure. We have to pass these parameters by reference, or address, because the recursive, and nesting, lambda engineering operates on the actual parameter objects. The & character in front of the parameter name defines the parameter as a reference parameter. To use the other option – pass by value – we would leave off the & character. If we do this, the lambda would receive its own individual copy of that parameter, and the engineering would fail. A recursive lambda requires its own name, in the closure brackets, as a reference parameter. For the outerRecLambda lambda, this becomes the &outerRecLambda parameter. The &innerRecLambda reference value points to the nested innerRecLambda lambda, which we will examine shortly. Finally, we placed the integer array data type value in the line 43 parentheses. This data type, at this location, covers the data type of the value that the lambda returns. The curly braces hold the lambda definition code.
When main() calls outerRecLambda at line 73, it passes the startValues array as an argument. Line 43 names the lambda outerRecLambda. Also at line 43, the startValues array becomes the x[] parameter. Lines 45 and 46 first map the array values to pentagonal numbers, and then test those numbers to see if they solve the problem. If yes, the lambda will return x[] to main() at line 64. Although the return at line 60 might look redundant, the code block from lines 58 to 62 could find the solution, so the line 60 return covers that possibility. If the latest x[] values don’t solve the problem, line 50 moves the smaller number to just after the larger number, and calls innerRecLambda, the second recursive lambda, at line 52. This matches the outer loop engineering in the loop solution above. innerRecLambda tests every n value pair between x[1] and 1. It returns a boolean value, and it works like the inner loop of the loop solution above. If innerRecLambda returns false, outerRecLambda resets the x[] array values at lines 54 and 55, and recursively calls itself at line 57. This value reset, combined with the recursive call, moves outerRecLambda closer to the solution.
The innerRecLambda declaration and definition at lines 22 and 23 have a similar structure to the outerRecLambda syntax. This lambda keeps x[1] fixed, and it tests all integer pairs between x[1] and 1. It matches the inner loop of the loop solution above. If it does not find a solution pair at line 28, it moves x[0] down by 1, and calls itself at line 32. At line 33, innerRecLambda sees that x[0] = 1, and if it did not find a solution pair, innerRecLambda ends and returns false back to outerRecLambda. If innerRecLambda did find the solution pair, it stops its recursion and returns true back to outerRecLambda at line 38. Both lambdas operate on the integer arrays passed as reference arguments to them. An array is a pointer. As a result, all lambda array operations happen on the same values in memory. When innerRecLambda finds the solution number pair, it only needs to return true at line 38. outerRecLambda will see those values because it both sees x[], and because x[] has an array data type. innerRecLambda also operates as an anonymous function. This flexibility means that we can recursively call it, with its argument, at line 32.
To run the software, drill down to
Debug -> Start Without Debugging
as shown:
In a test on a Windows 10 desktop, the output
shows the correct solution.
Here, we saw a nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Seven - Euler 44 Nested Recursion: Vectors will show a vector-based nested C++ recursive solution to that problem.
Part Five - Stack Configuration showed how to configure the stack for the nested C++ recursion solution we'll build for the Euler 44 Pentagonal Numbers problem. Here, we'll explore an actual nested C++ recursive solution to that problem.
This C++ recursive solution available here calculates the Euler Project #44 solution with nested recursive lambdas:
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7. #include <vector>
8.
9. bool is_pentnum(int x) {
10.
11. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
12. return (((testval - trunc(testval)) == 0.0) ? true : false);
13. };
14.
15. int gen_pentnum(int n) {
16.
17. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
18. };
19.
20. int main() {
21.
22. std::function<bool (int[])> innerRecLambda;
23. innerRecLambda = [&innerRecLambda](int x[]) {
24.
25. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
26. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
27.
28. if ((x[0] > 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29.
30. x[0]--;
31.
32. return innerRecLambda(x);
33. } else if ((x[0] == 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
34.
35. return false;
36. } else {
37.
38. return true;
39. }
40. };
41.
42. std::function<int* (int[])> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
44.
45. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
46. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
47.
48. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
49.
50. x[0] = x[1] - 1;
51.
52. if (!(innerRecLambda(x))) {
53.
54. x[0] = x[1];
55. x[1]++;
56.
57. return outerRecLambda(x);
58. } else {
59.
60. return (x);
61. }
62. } else {
63.
64. return (x);
65. }
66. };
67.
68. int startValues[2] = {1, 2};
69. int* finishedValues;
70.
71. auto startTime = std::chrono::high_resolution_clock::now();
72.
73. finishedValues = outerRecLambda(startValues);
74.
75. auto endTime = std::chrono::high_resolution_clock::now();
76. std::chrono::duration timeDifference = endTime - startTime;
77.
78. std::cout << "\n\tThe calculated x vector values --> pentagonal numbers: " << "\n\n";
79. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
80. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
81. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
82. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
83.
84. std::cout << std::boolalpha;
85.
86. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0])) << "\n\n";
87. std::cout << "\t______________________________________________\n";
88. std::cout << "\t______________________________________________\n\n\n";
89. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
90. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
91. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
92. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
93. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0])) << "\n\n";
94.
95. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
96.
97. system("pause");
98.}
Download the files for this solution from this GitHub resource. Line 68 defines integer array startValues, and initializes it to the first pair of n values. Line 69 declares integer array finishedValues. This stores the n values that map to the pentagonal number solution pair. Line 71 saves the starting time, and line 75 saves the ending time. Line 73 calls outerRecLambda() and passes the startValues array as an argument. This call returns the calculated solution pair to the finishedValues array.
This solution uses two lambdas, one declared at lines 22 and 23, and one declared at lines 42 and 43. Lines 42 and 43 declare the outerRecLambda lambda:
42. std::function<int* (int[])> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
This recursive lambda mirrors the outer loop in the Euler 44 nested loop solution we saw in Part Two - Pentagonal Numbers. Lambda declarations and definitions offer many options. Here, we need to declare and define a lambda value. On line 42, the std::function keywords “wrap” the lambda code in a class that we can use to assign the lambda to a variable. In this case, we’ll assign the lambda to the variable name outerRecLambda. outerRecLambda will return a pointer to an integer, and it has an input parameter of type integer array. In the angle brackets, int* declares the data type of the lambda return value. Inside the nested parentheses, int[] declares the input parameter data type of the lambda. outerRecLambda operates as a function variable, or an anonymous function. We can easily pass arguments to anonymous functions, and receive values from them. We can also call an anonymous function recursively. This flexibility means that we can recursively call outerRecLambda, with its argument, at line 57. Finally, the declaration names the lambda outerRecLambda at line 43.
Through a closure, a function can “see” objects and variables outside of its definition. In C++, lambdas support closures, and as a result, they can “see” objects and variables outside their formal definitions. This offers even more flexibility. The lambda definition syntax places the closure values in square brackets. The lambda definition starts on line 43, and in the square brackets, the &outerRecLambda and &innerRecLambda parameters form a closure. We have to pass these parameters by reference, or address, because the recursive, and nesting, lambda engineering operates on the actual parameter objects. The & character in front of the parameter name defines the parameter as a reference parameter. To use the other option – pass by value – we would leave off the & character. If we do this, the lambda would receive its own individual copy of that parameter, and the engineering would fail. A recursive lambda requires its own name, in the closure brackets, as a reference parameter. For the outerRecLambda lambda, this becomes the &outerRecLambda parameter. The &innerRecLambda reference value points to the nested innerRecLambda lambda, which we will examine shortly. Finally, we placed the integer array data type value in the line 43 parentheses. This data type, at this location, covers the data type of the value that the lambda returns. The curly braces hold the lambda definition code.
When main() calls outerRecLambda at line 73, it passes the startValues array as an argument. Line 43 names the lambda outerRecLambda. Also at line 43, the startValues array becomes the x[] parameter. Lines 45 and 46 first map the array values to pentagonal numbers, and then test those numbers to see if they solve the problem. If yes, the lambda will return x[] to main() at line 64. Although the return at line 60 might look redundant, the code block from lines 58 to 62 could find the solution, so the line 60 return covers that possibility. If the latest x[] values don’t solve the problem, line 50 moves the smaller number to just after the larger number, and calls innerRecLambda, the second recursive lambda, at line 52. This matches the outer loop engineering in the loop solution above. innerRecLambda tests every n value pair between x[1] and 1. It returns a boolean value, and it works like the inner loop of the loop solution above. If innerRecLambda returns false, outerRecLambda resets the x[] array values at lines 54 and 55, and recursively calls itself at line 57. This value reset, combined with the recursive call, moves outerRecLambda closer to the solution.
The innerRecLambda declaration and definition at lines 22 and 23 have a similar structure to the outerRecLambda syntax. This lambda keeps x[1] fixed, and it tests all integer pairs between x[1] and 1. It matches the inner loop of the loop solution above. If it does not find a solution pair at line 28, it moves x[0] down by 1, and calls itself at line 32. At line 33, innerRecLambda sees that x[0] = 1, and if it did not find a solution pair, innerRecLambda ends and returns false back to outerRecLambda. If innerRecLambda did find the solution pair, it stops its recursion and returns true back to outerRecLambda at line 38. Both lambdas operate on the integer arrays passed as reference arguments to them. An array is a pointer. As a result, all lambda array operations happen on the same values in memory. When innerRecLambda finds the solution number pair, it only needs to return true at line 38. outerRecLambda will see those values because it both sees x[], and because x[] has an array data type. innerRecLambda also operates as an anonymous function. This flexibility means that we can recursively call it, with its argument, at line 32.
To run the software, drill down to
Debug -> Start Without Debugging
as shown:
Here, we saw a nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Seven - Euler 44 Nested Recursion: Vectors will show a vector-based nested C++ recursive solution to that problem.