You may make the example a bit more challenging by employing
Divide and conquer algorithms[
^].
E.g. calculate the sum by calculating the sum of the left "half" plus the sum of the right "half" of your array.
int sum(int a[], int size)
{
int result = 0;
if (size == 1)
{
result = a[0];
}
else if (size > 1)
{
int midpoint = size/2;
int left = sum(a, midpoint);
int right = sum(a+midpoint, size-midpoint);
result = left + right;
}
return result;
}
For the purpose of this exercise, add some more arguments to trace the algorithm, e.g.
int sum(int a[], int from, int size, const string& context, int depth)
{
string indent(depth, '|');
cout << indent << context << "(a, " << from << ", " << size << ")" << endl;
int result = 0;
if (size == 1)
{
result = a[from];
}
else if (size > 1)
{
int midpoint = size/2;
int left = sum(a, from, midpoint, "left", depth+1);
int right = sum(a, from+midpoint, size-midpoint, "right", depth+1);
result = left + right;
cout << indent << "=" << left << "+" << right << endl;
}
cout << indent << "=" << result << endl;
return result;
}
...
int a[] = { 1,2,3,4,5,6,7,8,9, 10};
cout << "sum = " << sum(a, 0, 10, "sum", 0) << endl;
This results in
sum(a, 0, 10)
|left(a, 0, 5)
||left(a, 0, 2)
|||left(a, 0, 1)
|||=1
|||right(a, 1, 1)
|||=2
||=1+2
||=3
||right(a, 2, 3)
|||left(a, 2, 1)
|||=3
|||right(a, 3, 2)
||||left(a, 3, 1)
||||=4
||||right(a, 4, 1)
||||=5
|||=4+5
|||=9
||=3+9
||=12
|=3+12
|=15
|right(a, 5, 5)
||left(a, 5, 2)
|||left(a, 5, 1)
|||=6
|||right(a, 6, 1)
|||=7
||=6+7
||=13
||right(a, 7, 3)
|||left(a, 7, 1)
|||=8
|||right(a, 8, 2)
||||left(a, 8, 1)
||||=9
||||right(a, 9, 1)
||||=10
|||=9+10
|||=19
||=8+19
||=27
|=13+27
|=40
=15+40
=55
sum = 55
This is a more realistic situation(not for an array, but for some kind of problems). And the recursion depth is reduced too. You are not bound to calculate the left half and the right half. E.g. if you want to take benefit of concurrent calculation of some values, you may divide into multiple parts and conquer ;-)
Cheers
Andi