Question: I am trying to understand how the following algorithms works.

```
#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

```

First, what I am interested in is that in spite of algorithm's working correctly, it is mysterious for me how it finds the maximum element. I will show how I understood this algorithm:

Step 1: we say that in case of an array, `l=0` and `r=10`, it checks `if (l>r)` which does not hold of course so it calculates `m=(0+10)/2;`. Then do again the procedure for new bounds. The first pair is (0,5), the second is (6,10) and after the final operation it compares two returned values and finally returns the maximum element between them.

Does this algorithm always work? In each iteration it does not do any comparison, only the final step. How can it determine the maximum element at each recursive iteration? It checks only what. For example: take pair(0,5), is (0 more than 5)? No, so repeat again and divide these bounds into two so get new average value m1=(0+5)/2 then again again and return some element but not the maximum. Also for second subarray we can say the same.

What is the main idea of this algorithm?

Answer: 
Your error is here:

> 
> In each iteration it does not do any comparison, only the final step.
> 
> 
> 

This is wrong. In fact, it does a comparison in *every* step of the recursion (except in the base cases, i.e. where the array size is 1).
This answer might be so late, but it may be useful to someone to grasp the recursion calls, I modified the above code to trace out the function calls.
After seeing the output it is easy to see how a recursive tree is made.

```
#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
if (l == r)  
    return a[l];
int m = (l+r)/2;

cout<<"values gonna get computed in 1st recursive call"<< l<<" "<< m<<"\n";
int u = maxsimum(a,l,m);

cout<<"value of u "<<u<<"\n";

cout<<"value gonna get computed in 2nd recursion  call "<<m+1 <<" "<<r<<"\n";
int v = maxsimum(a,m+1,r);

cout<<"value of v : "<<v<<"\n";
cout<<"current u value :"<<u <<"current v value "<<v <<"\n";

return u>v?u:v;    
}

int main() {
int a[] = {5,6,7,8,9};
int n = sizeof(a)/sizeof(int);
cout << maxsimum(a,0,n-1) << endl;         
return 0;
}

```

Here is the recursion tree for the above program, the tree first goes towards the left side i.e for the first recursive statement, then each call returns its base value, the return condition makes sure only the maximum element is selected in each calls.

```
                 (9)  
                (0,4)
              /      \
           7 /        \9
        (0,2)          (3,4)
         /  \          /    \
       6/    \7      8/      \9
       (0,1)  (2,2)  (3,3)     (4,4) 
        / \      
      5/   \6
     (0,0) (1,1)

```