Updated Nested C++ Recursion

In an earlier article - Nested C++ Recursion - I described C++ nested recursive solutions to the Euler 44 Pentagonal Numbers problem. The basic engineering for those solutions works correctly, in the sense that they return the correct results. However, I realized that the engineering has a fatal flaw. This two-part article will explain the flaw, and how to fix that flaw. This GitHub resource hosts the updated C++ solutions described in this article.

As described in part six of the earlier article, this solution relies on arrays:

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

This image shows the flaw in the engineering:

The innerRecLambda function at line 22 above moves the first x array element (the left vertical line) towards 1. When that x[0] array element reaches 1020 and the second x[0] array element (the right vertical line) reaches 2167, the program ends because it found the solution. The x array values [1020, 2167] happen to be correct. However, a potential first array element could exist between 1 and 1019: [{1 ... 1019}, 2167]. The software never tests those values. Instead of moving the first array element down towards 1, the innerRecLambda function should reverse the way it moves that array element. In the new version of this function, the first array element starts at 1, so that the innerRecLambda function can move that array element to the right, towards the second array element. This ensures that the software tests all possible integer pairs before it finds the solution.

Here, we saw the problem with all the solutions in the earlier Nested C++ Recursion article. In Updated Nested C++ Recursion - Part Two, we'll explore the updated solution that fixes the problem.

Updated Nested C++ Recursion - Part One