further examples of recursion in the remainder of this we provide additional examples of the use of recursion we organize our presentation by considering the maximum number of recursive calls that may be started from within the body of single activation if recursive call starts at most one otherwe call this linear recursion if recursive call may start two otherswe call this binary recursion if recursive call may start three or more othersthis is multiple recursion linear recursion if recursive function is designed so that each invocation of the body makes at most one new recursive callthis is know as linear recursion of the recursions we have seen so farthe implementation of the factorial function (section and the good fibonacci function (section are clear examples of linear recursion more interestinglythe binary search algorithm (section is also an example of linear recursiondespite the "binaryterminology in the name the code for binary search (code fragment includes case analysis with two branches that lead to recursive callsbut only one of those calls can be reached during particular execution of the body consequence of the definition of linear recursion is that any recursion trace will appear as single sequence of callsas we originally portrayed for the factorial function in figure of section note that the linear recursion terminology reflects the structure of the recursion tracenot the asymptotic analysis of the running timefor examplewe have seen that binary search runs in (log ntime summing the elements of sequence recursively linear recursion can be useful tool for processing data sequencesuch as python list supposefor examplethat we want to compute the sum of sequencesof integers we can solve this summation problem using linear recursion by observing that the sum of all integers in is trivially if and otherwise that it is the sum of the first integers in plus the last element in (see figure figure computing the sum of sequence recursivelyby adding the last number to the sum of the first