Data structure and algorithm
Instructions
The instructions and starting templates for the assignment are attached to this module. Please download them and follow the instructions. You should submit your completed .cpp source files to this MyLeoOnline folder by the due date once you are done with the assignment.
There are actually 3 source files/starting templates for this assignment: assg-04.cpp, BinomialFunctions.hpp and BinomialFunctions.cpp. You need to download and use all 3. assg-04.cpp contains the main function and has tests of your code. You should not need to add anything to this file, simply uncomment the tests as you are working on your assignment. You should add your name and information to the file header at the top of all 3 files. The files BinomialFunctions.hpp and BinomialFunctions.cpp are the header file and implementation file respectively. You will need to add the function prototypes to the .hpp header file class definitions for the functions you are to write for this assignment. And likewise, you will need to write and implement your functions in the BinomialFunctions.cpp file.
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date January 22, 2019
* @assg Assignment 04
*
* @description Header file of definitions for implementation
* the Binomial Coefficient functions. We have functions for computing
* the factorial of an integer and for counting the number of combinations
* of n choose i items in this library.
*/
#ifndef _BINOMIALFUNCTIONS_H_
#define _BINOMIALFUNCTIONS_H_
#include
using namespace std;
// global definitions
typedef long long int bigint; // give long int an alias name of bigint
// Function prototypes for our BinomialFunctions library go here
#endif // _BINOMIALFUNCTIONS_H_
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date January 22, 2019
* @assg Assignment 04
*
* @description Implementation file of function implementations for
* the Binomial Coefficient functions. We have functions for computing
* the factorial of an integer and for counting the number of combinations
* of n choose i items in this library.
*/
#include “BinomialFunctions.hpp”
using namespace std;
Assg 0
4
: Recursio
n
COSC
2
3
3
6
Data Structures
Objectives
• Practice writing functions
• Practice writing recursive functions.
• Compare iterative vs. recursive implementation of functions.
• Learn to define base case and general case for recursion.
Description
In this assignment we will write a recursive function to calculate what is
known as the binomial coefficient. The binomial coefficient is a very useful
quantity, it allows us to count the number of combinations of selecting i items
out of a set of n elements. For example, if we have 3 items A, B, C, there are
3 ways to choose
1
element from the items: choose A, or choose B or choose
C. There are also 3 ways to choose 2 elements from the items: AB, AC, BC.
There is only 1 way to choose 3 elements from a set of 3 items: ABC. When
we choose 2 elements from a set of 3 items, we normally speak of this as
counting the number of combinations of 3 choose 2, and mathematically we
write this as a binomial coefficient(
3
2
)
= 3 (1)
Where the result of the binomial coefficient is to count up the number of
combinations we will have for n items when we select i elements. As another
example, just to make this clear, if we have a set of 4 items, ABCD, and we
choose 2 elements from this set, we get: AB, AC, AD, BC, BD, CD = 6:(
4
2
)
= 6 (2)
1
Notice that for the binomial coefficient order doesn’t matter, thus AB
and BA are considered the same when choosing 2 elements from the set of
4, and we end up with only a count of 6 ways to choose 2 items from a set
of 4 (look up permutations for a similar concept but where order matters).
Mathematically we can compute directly the number of combinations for
n choose i using factorials: (
n
i
)
=
n!
i!(n − i)!
(3)
Where ! represents the factorial of a number, as we discussed in our
textbook.
However, another way of computing the number of combinations is by
defining a recursive relationship:(
n
i
)
=
(
n − 1
i − 1
)
+
(
n − 1
i
)
(4)
You can think of this as the general case of a recursive function that takes
two parameters n and i, and computes the answer recursively by adding to-
gether two smaller subproblems. For this recursive definition of the binomial
coefficient, the base cases are:(
n
0
)
=
(
n
n
)
= 1 (
5
)
We have already seen why n items choose n elements will always be 1.
The other base case is used by definition, and simply means that there is
only 1 way of choosing no items from a set (e.g. you don’t choose).
In this assignment we will write several functions. First of all you will
write your own version of the factorial function. Actually I want you to write
two versions, a recursive version of factorial, and a version that uses a loop
(iterative version). We will be using long int (64-bit) instead of regular int
(32-bit) for all of the parameters and return values. You will find a typedef
given to you in the starting .hpp template:
typedef long int bigint;
A typedef like this is really just an alias or name for the other already
known type. In this case bigint means a long int. All of your parameters
and return values for the functions in this assignment should be defined to
be of type bitint. Why did we use the bigint? Well, the largest result
from factorial that will fit into a regular 32-bit int is 12! = 4
7
9
001600. By
2
using a 64-bit int, we can expand the maximum factorial we can calculate a
bit, where 20! = 243290200
8
176640000 and this fits into a 64-bit integer.
Then you will write two versions of the binomial coefficient to count
combinations. One version will use one of your factorial functions to directly
count the combinations, using the first formula given above. Then your
second version will be a recursive version, that uses the recursive general
and base case given to implement counting the number of combinations.
For this assignment you need to perform the following tasks.
1. Write a function called factorialIterative(). This function should
take a single BIG integer (bigint) as its parameter n, and it will com-
pute the factorial n! of the value and return it as its result (as a bigint).
Write this functions using a loop (do not use recursion).
2. Write the factorial function again, but using recursion. Call this func-
tion factorialRecursive(). The function takes the same parameters
and returns the same result as described in 1.
3. Write a function called countCombinationsDirectly(). This function
will compute the number of combinations that result from choosing i el-
ements from set of n items. The function should take two bigint values
as its parameters n and i, which will be integers >= 0. The function
should use the equation 3 above to directly compute the number of
combinations. You should use your factorialRecursive() function
to compute the factorials in this function.
4. Write a function called countCombinationsRecursive(). This func-
tion will also count the number of combinations of choosing i elements
from a set of n items. However, you need to implement this calcula-
tion as a recursive function, using the general and base cases described
above for counting combinations in equation 4 (general case) and equa-
tion 5 (base cases). Your function will take the same two bigint pa-
rameters as input n and i with values >= 0, and will return a bigint
result.
You will again be given 3 starting template files like before, an assg-04.cpp
file of tests of your code, and a BinomialFunctions.hpp and BinomialFunc-
tions.cpp header and implementation file. As before, you should practice
incremental development, and uncomment the tests in the assg-04.cpp file
one at a time, and implement the functions in the order shown. If you im-
plement your code correctly and uncomment all of the tests, you should get
the following correct output:
3
Testing iterative version factorialIterative()
————————————————————-
Test base case: factorialIterative(0) = 1
Test edge case: factorialIterative(1) = 1
Test error case: factorialIterative(-1) = 1
Test general case: factorialIterative(
10
) = 3628800
Test general case (largest 32 bit int): factorialIterative(12) = 479001600
Test general case (largest 64 bit int): factorialIterative(20) = 2432902008176640000
Elapsed time 10000 loops of factorialIterative(20) 0.000880682
Testing recursive version factorialRecursive()
————————————————————-
Test base case: factorialRecursive(0) = 1
Test edge case: factorialRecursive(1) = 1
Test error case: factorialRecursive(-1) = 1
Test general case: factorialRecursive(10) = 3628800
Test general case (largest 32 bit int): factorialRecursive(12) = 479001600
Test general case (largest 64 bit int): factorialRecursive(20) = 2432902008176640000
Test equivalence of iterative and recursive solutions from n=0 to 20:
Testing n = 0… passed
Testing n = 1… passed
Testing n = 2… passed
Testing n = 3… passed
Testing n = 4… passed
Testing n = 5… passed
Testing n = 6… passed
Testing n = 7… passed
Testing n = 8… passed
Testing n = 9… passed
Testing n = 10… passed
Testing n = 11… passed
Testing n = 12… passed
Testing n = 13… passed
Testing n = 14… passed
Testing n = 15… passed
Testing n = 16… passed
Testing n = 17… passed
Testing n = 18… passed
Testing n = 19… passed
Testing n = 20… passed
4
Elapsed time 10000 loops of factorialRecursive(20) 0.00179999
Testing combinations countCombinationsDirectly()
————————————————————-
Test base case: n=5 choose i=0: 1
Test base case: n=5 choose i=5: 1
Test edge case: n=0 choose i=0: 1
Test general case: n=5 choose i=1: 5
Test general case: n=4 choose i=2: 6
Test general case: n=15 choose i=6: 5005
Test general case: n=15 choose i=14: 15
Test general case: n=20 choose i=10: 184756
Elapsed time 10000 loops of countCombinationsDirectly(n=20 choose i=10) :0.00309266
Testing combinations countCombinationsRecursive()
————————————————————-
Test base case: n=5 choose i=0: 1
Test base case: n=5 choose i=5: 1
Test edge case: n=0 choose i=0: 1
Test general case: n=5 choose i=1: 5
Test general case: n=4 choose i=2: 6
Test general case: n=15 choose i=6: 5005
Test general case: n=15 choose i=14: 15
Test general case: n=20 choose i=10: 184756
Test equivalence of iterative and recursive solutions for counting combinations
This is an exhaustive test of all combinations of n and i from 0 to 15
Testing (n=0 choose i=0) equivalence… passed
Testing (n=1 choose i=0) equivalence… passed
Testing (n=1 choose i=1) equivalence… passed
Testing (n=2 choose i=0) equivalence… passed
Testing (n=2 choose i=1) equivalence… passed
Testing (n=2 choose i=2) equivalence… passed
Testing (n=3 choose i=0) equivalence… passed
Testing (n=3 choose i=1) equivalence… passed
Testing (n=3 choose i=2) equivalence… passed
Testing (n=3 choose i=3) equivalence… passed
Testing (n=4 choose i=0) equivalence… passed
Testing (n=4 choose i=1) equivalence… passed
Testing (n=4 choose i=2) equivalence… passed
Testing (n=4 choose i=3) equivalence… passed
5
Testing (n=4 choose i=4) equivalence… passed
Testing (n=5 choose i=0) equivalence… passed
Testing (n=5 choose i=1) equivalence… passed
Testing (n=5 choose i=2) equivalence… passed
Testing (n=5 choose i=3) equivalence… passed
Testing (n=5 choose i=4) equivalence… passed
Testing (n=5 choose i=5) equivalence… passed
Testing (n=6 choose i=0) equivalence… passed
Testing (n=6 choose i=1) equivalence… passed
Testing (n=6 choose i=2) equivalence… passed
Testing (n=6 choose i=3) equivalence… passed
Testing (n=6 choose i=4) equivalence… passed
Testing (n=6 choose i=5) equivalence… passed
Testing (n=6 choose i=6) equivalence… passed
Testing (n=7 choose i=0) equivalence… passed
Testing (n=7 choose i=1) equivalence… passed
Testing (n=7 choose i=2) equivalence… passed
Testing (n=7 choose i=3) equivalence… passed
Testing (n=7 choose i=4) equivalence… passed
Testing (n=7 choose i=5) equivalence… passed
Testing (n=7 choose i=6) equivalence… passed
Testing (n=7 choose i=7) equivalence… passed
Testing (n=8 choose i=0) equivalence… passed
Testing (n=8 choose i=1) equivalence… passed
Testing (n=8 choose i=2) equivalence… passed
Testing (n=8 choose i=3) equivalence… passed
Testing (n=8 choose i=4) equivalence… passed
Testing (n=8 choose i=5) equivalence… passed
Testing (n=8 choose i=6) equivalence… passed
Testing (n=8 choose i=7) equivalence… passed
Testing (n=8 choose i=8) equivalence… passed
Testing (n=9 choose i=0) equivalence… passed
Testing (n=9 choose i=1) equivalence… passed
Testing (n=9 choose i=2) equivalence… passed
Testing (n=9 choose i=3) equivalence… passed
Testing (n=9 choose i=4) equivalence… passed
Testing (n=9 choose i=5) equivalence… passed
Testing (n=9 choose i=6) equivalence… passed
Testing (n=9 choose i=7) equivalence… passed
Testing (n=9 choose i=8) equivalence… passed
6
Testing (n=9 choose i=9) equivalence… passed
Testing (n=10 choose i=0) equivalence… passed
Testing (n=10 choose i=1) equivalence… passed
Testing (n=10 choose i=2) equivalence… passed
Testing (n=10 choose i=3) equivalence… passed
Testing (n=10 choose i=4) equivalence… passed
Testing (n=10 choose i=5) equivalence… passed
Testing (n=10 choose i=6) equivalence… passed
Testing (n=10 choose i=7) equivalence… passed
Testing (n=10 choose i=8) equivalence… passed
Testing (n=10 choose i=9) equivalence… passed
Testing (n=10 choose i=10) equivalence… passed
Testing (n=11 choose i=0) equivalence… passed
Testing (n=11 choose i=1) equivalence… passed
Testing (n=11 choose i=2) equivalence… passed
Testing (n=11 choose i=3) equivalence… passed
Testing (n=11 choose i=4) equivalence… passed
Testing (n=11 choose i=5) equivalence… passed
Testing (n=11 choose i=6) equivalence… passed
Testing (n=11 choose i=7) equivalence… passed
Testing (n=11 choose i=8) equivalence… passed
Testing (n=11 choose i=9) equivalence… passed
Testing (n=11 choose i=10) equivalence… passed
Testing (n=11 choose i=11) equivalence… passed
Testing (n=12 choose i=0) equivalence… passed
Testing (n=12 choose i=1) equivalence… passed
Testing (n=12 choose i=2) equivalence… passed
Testing (n=12 choose i=3) equivalence… passed
Testing (n=12 choose i=4) equivalence… passed
Testing (n=12 choose i=5) equivalence… passed
Testing (n=12 choose i=6) equivalence… passed
Testing (n=12 choose i=7) equivalence… passed
Testing (n=12 choose i=8) equivalence… passed
Testing (n=12 choose i=9) equivalence… passed
Testing (n=12 choose i=10) equivalence… passed
Testing (n=12 choose i=11) equivalence… passed
Testing (n=12 choose i=12) equivalence… passed
Testing (n=13 choose i=0) equivalence… passed
Testing (n=13 choose i=1) equivalence… passed
Testing (n=13 choose i=2) equivalence… passed
7
Testing (n=13 choose i=3) equivalence… passed
Testing (n=13 choose i=4) equivalence… passed
Testing (n=13 choose i=5) equivalence… passed
Testing (n=13 choose i=6) equivalence… passed
Testing (n=13 choose i=7) equivalence… passed
Testing (n=13 choose i=8) equivalence… passed
Testing (n=13 choose i=9) equivalence… passed
Testing (n=13 choose i=10) equivalence… passed
Testing (n=13 choose i=11) equivalence… passed
Testing (n=13 choose i=12) equivalence… passed
Testing (n=13 choose i=13) equivalence… passed
Testing (n=14 choose i=0) equivalence… passed
Testing (n=14 choose i=1) equivalence… passed
Testing (n=14 choose i=2) equivalence… passed
Testing (n=14 choose i=3) equivalence… passed
Testing (n=14 choose i=4) equivalence… passed
Testing (n=14 choose i=5) equivalence… passed
Testing (n=14 choose i=6) equivalence… passed
Testing (n=14 choose i=7) equivalence… passed
Testing (n=14 choose i=8) equivalence… passed
Testing (n=14 choose i=9) equivalence… passed
Testing (n=14 choose i=10) equivalence… passed
Testing (n=14 choose i=11) equivalence… passed
Testing (n=14 choose i=12) equivalence… passed
Testing (n=14 choose i=13) equivalence… passed
Testing (n=14 choose i=14) equivalence… passed
Testing (n=15 choose i=0) equivalence… passed
Testing (n=15 choose i=1) equivalence… passed
Testing (n=15 choose i=2) equivalence… passed
Testing (n=15 choose i=3) equivalence… passed
Testing (n=15 choose i=4) equivalence… passed
Testing (n=15 choose i=5) equivalence… passed
Testing (n=15 choose i=6) equivalence… passed
Testing (n=15 choose i=7) equivalence… passed
Testing (n=15 choose i=8) equivalence… passed
Testing (n=15 choose i=9) equivalence… passed
Testing (n=15 choose i=10) equivalence… passed
Testing (n=15 choose i=11) equivalence… passed
Testing (n=15 choose i=12) equivalence… passed
Testing (n=15 choose i=13) equivalence… passed
8
Testing (n=15 choose i=14) equivalence… passed
Testing (n=15 choose i=15) equivalence… passed
Elapsed time 10000 loops of countCombinationsRecursive(n=20 choose i=10) :11.1177
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You
should attach and upload your completed .cpp source files to the submission
folder to complete this assignment. You really do not need to give me the
assg-04.cpp file again, as I will have my own file with additional tests of
your functions. However, please leave the names of the other two files as
BinomialFunctions.hpp and BinomialFunctions.cpp when you submit them.
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to
be graded. 0 if not satisfied.
2. 20 pts for implementing the factorialIterative() function correctly.
3. 25 pts for implementing the factorialRecursive() function correctly.
4. 15 pts for implementing the countCombinationsDirectly() function
correctly.
5. 30 pts for implementing the countCombinationsRecursive() function
correctly.
6. 5 pts. All output is correct and matches the correct example output.
7. 5 pts. Followed class style guidelines, especially those mentioned below.
Program Style
Your programs must conform to the style and formatting guidelines given
for this class. The following is a list of the guidelines that are required for
the assignment to be submitted this week.
1. Most importantly, make sure you figure out how to set your indentation
settings correctly. All programs must use 2 spaces for all indentation
9
levels, and all indentation levels must be correctly indented. Also all
tabs must be removed from files, and only 2 spaces used for indentation.
2. A function header must be present for member functions you define.
You must give a short description of the function, and document all of
the input parameters to the function, as well as the return value and
data type of the function if it returns a value for the member functions,
just like for regular functions. However, setter and getter methods do
not require function headers.
3. You should have a document header for your class. The class header
document should give a description of the class. Also you should doc-
ument all private member variables that the class manages in the class
document header.
4. Do not include any statements (such as system(“pause”) or inputting
a key from the user to continue) that are meant to keep the terminal
from going away. Do not include any code that is specific to a single
operating system, such as the system(“pause”) which is Microsoft
Windows specific.
10
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date January 12, 2019
* @assg Assignment 04
*
* @description Assignment 04 Practice defining recursive functions. We
* implement factorial and counting combinations functions using the
* binomial coefficient in this assignment. This file containts unit
* tests of the required functions for this assignment.
*/
#include
#include
#include
#include “BinomialFunctions.hpp”
using namespace std;
/** main
* The main entry point for this program. Execution of this program
* will begin with this main function.
*
* @param argc The command line argument count which is the number of
* command line arguments provided by user when they started
* the program.
* @param argv The command line arguments, an array of character
* arrays.
*
* @returns An int value indicating program exit status. Usually 0
* is returned to indicate normal exit and a non-zero value
* is returned to indicate an error condition.
*/
int main(int argc, char** argv)
{
// test iterative version of factorial
cout << "Testing iterative version factorialIterative() " << endl;
cout << "-------------------------------------------------------------" << endl;
bigint res;
//res = factorialIterative(0);
//cout << "Test base case: factorialIterative(0) = " << res << endl;
//assert(res == 1);
//res = factorialIterative(1);
//cout << "Test edge case: factorialIterative(1) = " << res << endl;
//assert(res == 1);
//res = factorialIterative(-1);
//cout << "Test error case: factorialIterative(-1) = " << res << endl;
//assert(res == 1);
//res = factorialIterative(10);
//cout << "Test general case: factorialIterative(10) = " << res << endl;
//assert(res == 3628800);
//res = factorialIterative(12);
//cout << "Test general case (largest 32 bit int): factorialIterative(12) = " << res << endl;
//assert(res == 479001600);
//res = factorialIterative(20);
//cout << "Test general case (largest 64 bit int): factorialIterative(20) = " << res << endl;
//assert(res == 2432902008176640000);
// timing test for factorialIterative, do it 10000 times and see how much time
// elapses
// https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
const int NUM_TIMING_LOOPS = 10000;
//auto start = chrono::high_resolution_clock::now();
//for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
//{
// res = factorialIterative(20);
//}
//auto finish = chrono::high_resolution_clock::now();
//chrono::duration
//cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialIterative(20) "
// << elapsed.count() << endl;
// test recursive version of factorial
cout << endl;
cout << "Testing recursive version factorialRecursive() " << endl;
cout << "-------------------------------------------------------------" << endl;
//res = factorialRecursive(0);
//cout << "Test base case: factorialRecursive(0) = " << res << endl;
//assert(res == 1);
//res = factorialRecursive(1);
//cout << "Test edge case: factorialRecursive(1) = " << res << endl;
//assert(res == 1);
//res = factorialRecursive(-1);
//cout << "Test error case: factorialRecursive(-1) = " << res << endl;
//assert(res == 1);
//res = factorialRecursive(10);
//cout << "Test general case: factorialRecursive(10) = " << res << endl;
//assert(res == 3628800);
//res = factorialRecursive(12);
//cout << "Test general case (largest 32 bit int): factorialRecursive(12) = " << res << endl;
//assert(res == 479001600);
//res = factorialRecursive(20);
//cout << "Test general case (largest 64 bit int): factorialRecursive(20) = " << res << endl;
//assert(res == 2432902008176640000);
//cout << "Test equivalence of iterative and recursive solutions from n=0 to 20: " << endl;
//for (int n = 0; n <= 20; n++)
//{
// cout << " Testing n = " << n << "...";
// assert(factorialIterative(n) == factorialRecursive(n));
// cout << " passed" << endl;
//}
// timing test for factorialRecursive, do it 10000 times and see how much time
// elapses
// https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
//start = chrono::high_resolution_clock::now();
//for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
//{
// res = factorialRecursive(20);
//}
//finish = chrono::high_resolution_clock::now();
//elapsed = finish - start;
//cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialRecursive(20) "
// << elapsed.count() << endl;
// test direct calculation version of counting combinations
cout << endl;
cout << "Testing combinations countCombinationsDirectly() " << endl;
cout << "-------------------------------------------------------------" << endl;
int i;
int n;
//n=5; i=0;
//res = countCombinationsDirectly(n, i);
//cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=5; i=5;
//res = countCombinationsDirectly(n, i);
//cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=0; i=0;
//res = countCombinationsDirectly(n, i);
//cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=5; i=1;
//res = countCombinationsDirectly(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 5);
//n=4; i=2;
//res = countCombinationsDirectly(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 6);
//n=15; i=6;
//res = countCombinationsDirectly(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 5005);
//n=15; i=14;
//res = countCombinationsDirectly(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 15);
// max factorial using bigint
//n=20; i=10;
//res = countCombinationsDirectly(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 184756);
// timing test for countCobminationsDirectory, do it 10000 times and see how much time
// elapses
// https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
//start = chrono::high_resolution_clock::now();
//for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
//{
// n=20; i=10;
// res = countCombinationsDirectly(n, i);
//}
//finish = chrono::high_resolution_clock::now();
//elapsed = finish - start;
//cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsDirectly("
// << "n=" << n << " choose i=" << i << ") :"
// << elapsed.count() << endl;
// test recursive calculation version of counting combinations
cout << endl;
cout << "Testing combinations countCombinationsRecursive() " << endl;
cout << "-------------------------------------------------------------" << endl;
//n=5; i=0;
//res = countCombinationsRecursive(n, i);
//cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=5; i=5;
//res = countCombinationsRecursive(n, i);
//cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=0; i=0;
//res = countCombinationsRecursive(n, i);
//cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 1);
//n=5; i=1;
//res = countCombinationsRecursive(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 5);
//n=4; i=2;
//res = countCombinationsRecursive(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 6);
//n=15; i=6;
//res = countCombinationsRecursive(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 5005);
//n=15; i=14;
//res = countCombinationsRecursive(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 15);
// max factorial using bigint
//n=20; i=10;
//res = countCombinationsRecursive(n, i);
//cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
//assert(res == 184756);
//cout << "Test equivalence of iterative and recursive solutions for counting combinations" << endl
// << "This is an exhaustive test of all combinations of n and i from 0 to 15" << endl;
//for (n = 0; n <= 15; n++)
//{
// for (i = 0; i <= n; i++)
// {
// cout << " Testing (n=" << n << " choose i=" << i << ") equivalence...";
// assert(countCombinationsDirectly(n, i) == countCombinationsRecursive(n, i));
// cout << " passed" << endl;
// }
//}
// timing test for countCobminationsRecursive, do it 10000 times and see how much time
// elapses
// https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
//start = chrono::high_resolution_clock::now();
//for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
//{
// n=20; i=10;
// res = countCombinationsRecursive(n, i);
//}
//finish = chrono::high_resolution_clock::now();
//elapsed = finish - start;
//cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsRecursive("
// << "n=" << n << " choose i=" << i << ") :"
// << elapsed.count() << endl;
// return 0 to indicate successful completion
return 0;
}