when an algorithm makes two recursive callswe say that it uses binary recursion these calls canfor examplebe used to solve two similar halves of some problemas we did in section for drawing an english ruler as another application of binary recursionlet us revisit the problem of summing the elements of an integer array in this casewe can sum the elements in by(irecursively summing the elements in the first half of (iirecursively summing the elements in the second half of aand (iiiadding these two values together we give the details in the algorithm of code fragment which we initially call as binarysum( , ,ncode fragment summing the elements in an array using binary recursion to analyze algorithm binarysumwe considerfor simplicitythe case where is power of two the general case of arbitrary is considered in exercise - figure shows the recursion trace of an execution of method binarysum( , we label each box with the values of parameters and nwhich represent the starting index and length of the sequence of elements to be reversedrespectively notice that the arrows in the trace go from box labeled ( ,nto another box labeled ( , / or ( / , / that isthe value of parameter is halved at each recursive call thusthe depth of the recursionthat isthe maximum number of method instances that are active at the same timeis log thusalgorithm binarysum uses an amount of additional space roughly proportional to this value this is big improvement over the space needed by the linearsum method of code fragment the running time of algorithm binarysum is still roughly