help with binary sum

[4ET0pfjN]

I'm trying to trace this function, and I know I'm supposed to complete the first recursive call BEFORE starting the second, but when I am drawing the stack, the first recursive call has its own left and right recursive calls so I get lost. Is anyone familiar with explaining how I would go about tracing properly.

int binarySum(int* arr, int i, int n) 
{
   if (n == 1)
      return arr[i];
   return binarySum(arr, i, ceil(n/2)) + binarySum(arr,i + ceil(n/2), floor(n/2));
}

[JLBorges]

Indent the trace messages with the depth of recursion.

C++ is a language with a strong notion of initialization and deinitialization; unlike in most other programming languages, we can just use RAII. For instance:

#include <iostream>
#include <string>

struct tracer
{
    enum { TABSZ = 4 } ;

    inline tracer( const int* a, std::size_t begin, std::size_t n )
    {
         std::cout << std::string( depth * TABSZ, ' ' )
                   << '(' << begin << ',' << n << ") => [ " ;
         for( std::size_t i = begin ; i < begin+n ; ++i ) std::cout << a[i] << ' ' ;
         std::cout << "]\n" ;
        ++depth ;
    }

    inline ~tracer() { --depth ; }

    private: static int depth ;
};

int tracer::depth = 0 ;

int sum( const int* a, std::size_t begin, std::size_t n )
{
    tracer t( a, begin, n ) ;
    return n==1 ? a[begin] : sum( a, begin, n/2 ) + sum( a, begin+n/2, (n+1)/2 ) ;
}

Prefer using integer arithmetic - it is exact.

[4ET0pfjN]

The reason I want to use it, even though when I trace by diagram it's messy is b/c quick sort, and merge sort use binary recursion so I figure any non-linear recursion must be important. I will try your code out, thanks. Recursion is one of those topics a programmer cannot dodge even though I wasn't taught properly in university, such as pointers and 2D, 3D or even higher arrays.