recursive algorithm for computing the sum of sequence of numbers based on this intuition is implemented in code fragment def linear sum(sn) """return the sum of the first numbers of sequence "" if = return else return linear sum(sn- [ - code fragment summing the elements of sequence using linear recursion recursion trace of the linear sum function for small example is given in figure for an input of size nthe linear sum algorithm makes function calls henceit will take (ntimebecause it spends constant amount of time performing the nonrecursive part of each call moreoverwe can also see that the memory space used by the algorithm (in addition to the sequence sis also ( )as we use constant amount of memory space for each of the activation records in the trace at the time we make the final recursive call (with return [ linear sum( return [ linear sum( return [ linear sum( return [ linear sum( return [ linear sum( return linear sum( figure recursion trace for an execution of linear sum( with input parameter [