binary recursion when function makes two recursive callswe say that it uses binary recursion we have already seen several examples of binary recursionmost notably when drawing the english ruler (section )or in the bad fibonacci function of section as another application of binary recursionlet us revisit the problem of summing the elements of sequencesof numbers computing the sum of one or zero elements is trivial with two or more elementswe can recursively compute the sum of the first halfand the sum of the second halfand add these sums together our implementation of such an algorithmin code fragment is initially invoked as binary sum( len( ) def binary sum(sstartstop) """return the sum of the numbers in implicit slice [start:stop"" if start >stopzero elements in slice return elif start =stop- one element in slice return [start elsetwo or more elements in slice mid (start stop/ return binary sum(sstartmidbinary sum(smidstopcode fragment summing the elements of sequence using binary recursion to analyze algorithm binary sumwe considerfor simplicitythe case where is power of two figure shows the recursion trace of an execution of binary sum( we label each box with the values of parameters start:stop for that call the size of the range is divided in half at each recursive calland so the depth of the recursion is log thereforebinary sum uses (log namount of additional spacewhich is big improvement over the (nspace used by the linear sum function of code fragment howeverthe running time of binary sum is ( )as there are function callseach requiring constant time : : : : : : : : : : : : : : : figure recursion trace for the execution of binary sum(