Updated Nested C++ Recursion - Part Two
Part One - Recursion Basics explained a problem with the engineering in my earlier Nested C++ Recursion article. Part Two here describes the updated C++ engineering. You can find all of the updated Visual Studio solutions at this GitHub resource.
This image shows how the original outerRecLambda function works:
Say that the outerRecLambda function at line 42 from Part 1 of this article starts at solution x array values [1, 14]. The outerRecLambda function resets the array values to [14, 15] as shown in the image. Instead, it should reset the array to [1, 15]. This outerRecLambda function works correctly:
1. std::function<int* (int[])> outerRecLambda;
2. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
3. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
4. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
5. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
6. if (!(innerRecLambda(x))) {
7. x[1]++;
8. x[0] = 1;
9. return outerRecLambda(x);
10. }
11. else {
12. return (x);
13. }
14. }
15. else {
16. return (x);
17. }
18. };
Here, lines 3 and 4 map the array values to pentagonal numbers. Line 5 tests those values to see if they solve the problem. If either of those values fails the test, outerRecLambda calls innerRecLambda at line 6 to test every integer pair between 1 and (x[1] - 1). If that test fails, line 7 moves x[1] to the right by 1, line 8 resets x[0] to 1, and line 9 recursively calls outerRecLambda. If outerRecLambda started at x array values [13, 14], it reset the x array to [1, 15], as shown in this diagram:
Since we repaired the outerRecLambda function, we must also repair the innerRecLambda function, as shown here:
1. std::function<bool (int[])> innerRecLambda;
2. innerRecLambda = [&innerRecLambda](int x[]) {
3.
4. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
5. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
6.
7. if ((x[0] < (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
8.
9. x[0]++;
10.
11. return innerRecLambda(x);
12. } else if ((x[0] == (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
13.
14. return false;
15. } else {
17. return true;
18. }
19. };
This function keeps x[1] fixed, and it tests all x[0] values between 1 and (x[1] - 1). If it does not find a solution pair at line 7, it adds 1 to x[0] at line 9, and recursively calls itself at line 11. The original innerRecLambda function at line 22 from Part 1 of this article starts at solution moved x[0] down by 1 in its code, in roughly this equivalent area. At line 12 here, innerRecLambda sees that x[0] = (x[1] - 1). In other words, innerRecLambda sees that x[0] has moved to 1 below x[1]. If it does not find a solution pair at that point in the code, innerRecLambda ends and returns false back to outerRecLambda at line 14. The original innerRecLambda saw that (x[0] - 1) at that equivalent point in its code. If this updated innerRecLambda function did find the solution pair, it stops its recursion and returns true back to outerRecLambda at line 17. Both lambda functions here 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 17. 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 11.
This is the complete array solution
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7.
8. bool is_pentnum(int x) {
10. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
11. return (((testval - trunc(testval)) == 0.0) ? true : false);
12. };
13.
14. int gen_pentnum(int n) {
16. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
17. };
18.
19. int main() {
20. std::function<bool (int[])> innerRecLambda;
21. innerRecLambda = [&innerRecLambda](int x[]) {
22. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
23. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
24. if ((x[0] < (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
25. x[0]++;
26. return innerRecLambda(x);
27. }
28. else if ((x[0] == (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29. return false;
30. }
31. else {
32. return true;
33. }
34. };
35.
36. std::function<int* (int[])> outerRecLambda;
37. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
38. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
39. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
40. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
41. if (!(innerRecLambda(x))) {
42. x[1]++;
43. x[0] = 1;
44. return outerRecLambda(x);
45. }
46. else {
47. return (x);
48. }
49. }
50. else {
51. return (x);
52. }
53. };
54.
55. int startValues[2] = { 1, 2 };
56. int* finishedValues;
57. auto startTime = std::chrono::high_resolution_clock::now();
58. finishedValues = outerRecLambda(startValues);
59. auto endTime = std::chrono::high_resolution_clock::now();
60. std::chrono::duration<double> timeDifference = endTime - startTime;
61. std::cout << "\n\tThe calculated x array values --> pentagonal numbers: " << "\n\n";
62. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
63. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
64. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
65. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
66.
67. std::cout << std::boolalpha;
68.
69. 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";
70. std::cout << "\t______________________________________________\n";
71. std::cout << "\t______________________________________________\n\n\n";
72. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
73. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
74. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
75. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
76. 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";
77.
78. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
79. }
and it correctly tests all integer pairs, from [1, 2], and calculates the correct solution. All the solutions at this GitHub resource have this revised engineering.
Sometimes, we build software with subtle bugs and flaws. It's never too late to fix the products we build.
This image shows how the original outerRecLambda function works:
Say that the outerRecLambda function at line 42 from Part 1 of this article starts at solution x array values [1, 14]. The outerRecLambda function resets the array values to [14, 15] as shown in the image. Instead, it should reset the array to [1, 15]. This outerRecLambda function works correctly:
1. std::function<int* (int[])> outerRecLambda;
2. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
3. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
4. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
5. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
6. if (!(innerRecLambda(x))) {
7. x[1]++;
8. x[0] = 1;
9. return outerRecLambda(x);
10. }
11. else {
12. return (x);
13. }
14. }
15. else {
16. return (x);
17. }
18. };
Here, lines 3 and 4 map the array values to pentagonal numbers. Line 5 tests those values to see if they solve the problem. If either of those values fails the test, outerRecLambda calls innerRecLambda at line 6 to test every integer pair between 1 and (x[1] - 1). If that test fails, line 7 moves x[1] to the right by 1, line 8 resets x[0] to 1, and line 9 recursively calls outerRecLambda. If outerRecLambda started at x array values [13, 14], it reset the x array to [1, 15], as shown in this diagram:
Since we repaired the outerRecLambda function, we must also repair the innerRecLambda function, as shown here:
1. std::function<bool (int[])> innerRecLambda;
2. innerRecLambda = [&innerRecLambda](int x[]) {
3.
4. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
5. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
6.
7. if ((x[0] < (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
8.
9. x[0]++;
10.
11. return innerRecLambda(x);
12. } else if ((x[0] == (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
13.
14. return false;
15. } else {
17. return true;
18. }
19. };
This function keeps x[1] fixed, and it tests all x[0] values between 1 and (x[1] - 1). If it does not find a solution pair at line 7, it adds 1 to x[0] at line 9, and recursively calls itself at line 11. The original innerRecLambda function at line 22 from Part 1 of this article starts at solution moved x[0] down by 1 in its code, in roughly this equivalent area. At line 12 here, innerRecLambda sees that x[0] = (x[1] - 1). In other words, innerRecLambda sees that x[0] has moved to 1 below x[1]. If it does not find a solution pair at that point in the code, innerRecLambda ends and returns false back to outerRecLambda at line 14. The original innerRecLambda saw that (x[0] - 1) at that equivalent point in its code. If this updated innerRecLambda function did find the solution pair, it stops its recursion and returns true back to outerRecLambda at line 17. Both lambda functions here 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 17. 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 11.
This is the complete array solution
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7.
8. bool is_pentnum(int x) {
10. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
11. return (((testval - trunc(testval)) == 0.0) ? true : false);
12. };
13.
14. int gen_pentnum(int n) {
16. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
17. };
18.
19. int main() {
20. std::function<bool (int[])> innerRecLambda;
21. innerRecLambda = [&innerRecLambda](int x[]) {
22. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
23. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
24. if ((x[0] < (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
25. x[0]++;
26. return innerRecLambda(x);
27. }
28. else if ((x[0] == (x[1] - 1)) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29. return false;
30. }
31. else {
32. return true;
33. }
34. };
35.
36. std::function<int* (int[])> outerRecLambda;
37. outerRecLambda = [&outerRecLambda, &innerRecLambda](int x[]) {
38. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
39. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
40. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
41. if (!(innerRecLambda(x))) {
42. x[1]++;
43. x[0] = 1;
44. return outerRecLambda(x);
45. }
46. else {
47. return (x);
48. }
49. }
50. else {
51. return (x);
52. }
53. };
54.
55. int startValues[2] = { 1, 2 };
56. int* finishedValues;
57. auto startTime = std::chrono::high_resolution_clock::now();
58. finishedValues = outerRecLambda(startValues);
59. auto endTime = std::chrono::high_resolution_clock::now();
60. std::chrono::duration<double> timeDifference = endTime - startTime;
61. std::cout << "\n\tThe calculated x array values --> pentagonal numbers: " << "\n\n";
62. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
63. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
64. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
65. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
66.
67. std::cout << std::boolalpha;
68.
69. 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";
70. std::cout << "\t______________________________________________\n";
71. std::cout << "\t______________________________________________\n\n\n";
72. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
73. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
74. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
75. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
76. 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";
77.
78. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
79. }
and it correctly tests all integer pairs, from [1, 2], and calculates the correct solution. All the solutions at this GitHub resource have this revised engineering.
Sometimes, we build software with subtle bugs and flaws. It's never too late to fix the products we build.