Note: with C++14
& C++17
life gets much better with constexpr
. Details: computing-exp-at-compile-time
and constexpr2
factorial(number) = 1 * 2 * 3 * … * (n-1) * n
1
2
3
4
5
6
7
8
9
| static int factorial_imperative(int value)
{
int factorial = 1;
for(auto idx = value; idx > 1; --idx )
{
factorial *= idx;
}
return factorial;
}
|
- Very compact code, which is good as well as bad for it can be difficult to understand at times
- Understanding when to stop, specifying termination condition correctly
So here is the recursive and immutable version for evaluating factorial:
1
2
3
4
5
6
| static int factorial_recursive(int value)
{
return
value <= 1 ? 1 :
(value * factorial_recursive(value-1));
}
|
- we are not mutating any variable, even though we generate new values due to recursion but we are not mutating
- well defined termination condition, at line 4: value <= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| // in metaprogram every thing is a template-class/struct
template<int Num>
struct factorial_c
{
enum
{
value = Num * factorial_c<Num-1>::value
};
};
// terminating conditions
//
// factorial of 1 is 1
//
template<>
struct factorial_c<1>
{
enum
{
value = 1
};
};
// factorial of 0 is 1
//
template<>
struct factorial_c<0>
{
enum
{
value = 1
};
};
int main()
{
auto factorial_5 = factorial_c<5>::value;
std::cout << "factorial of 5 is "
<< factorial_5 << std::endl;
return 0;
}
|
Here is how the compiler evaluates the template recusions:
1
2
3
4
5
6
7
| factorial_5 = factorial_c<5>::value;
factorial_5 = 5 * factorial_c<4>::value;
factorial_5 = 5 * 4 * factorial_c<3>::value;
factorial_5 = 5 * 4 * 3 * factorial_c<2>::value;
factorial_5 = 5 * 4 * 3 * 2 * factorial_c<1>::value;
factorial_5 = 5 * 4 * 3 * 2 * 1;
factorial_5 = 120;
|
Recursive & Immutable runtime code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static int gcd_recursive(int a, int b)
{
if( a == b )
{
return a;
}
//
auto max = a > b ? a : b;
auto min = a < b ? a : b;
//
//
if( min == 0 )
{
return max;
}
return gcd_recursive(min, max % min);
}
|
TMP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| // equivalent to max function
//
template<int One, int Two>
struct max_c
{
enum
{
value = One > Two ? One : Two
};
};
//
//
// equivalent to min function
//
template<int One, int Two>
struct min_c
{
enum
{
value = One < Two ? One : Two
};
};
//
//
// TMP version of gcd
//
template<int One, int Two>
struct gcd_c
{
enum
{
// equivalent to:
// value = gcd(min, max % min)
//
value = gcd_c< min_c<One, Two>::value,
max_c<One, Two>::value %
min_c<One,Two>::value>::value
};
};
//
//
// template specialization for
// Min being 0, this is our
// termination condition for recursion
//
template<int Max>
struct gcd_c<Max, 0>
{
enum
{
value = Max
};
};
|
lcm (least common multiple)
Recursive & Immutable runtime code:
1
2
3
4
| static int lcm_r(int one, int two)
{
return one * two / gcd_recursive(one, two);
}
|
TMP:
1
2
3
4
5
6
7
8
| template<int One, int Two>
struct lcm_c
{
enum
{
value = One * Two / gcd_c<One, Two>::value
};
};
|
Parting Thoughts
Well I don’t have summary for this post, as it is not yet finished. We have barely scratched the surface of this beast. C++ TMP has a complete language of its own, well thats what Boost.MPL library is all about. I will follow up on TMP with few more posts.
Related: