reversing sequence with recursion nextlet us consider the problem of reversing the elements of sequencesso that the first element becomes the lastthe second element becomes second to the lastand so on we can solve this problem using linear recursionby observing that the reversal of sequence can be achieved by swapping the first and last elements and then recursively reversing the remaining elements we present an implementation of this algorithm in code fragment using the convention that the first time we call this algorithm we do so as reverse( len( ) def reverse(sstartstop) """reverse elements in implicit slice [start:stop"" if start stop if at least elements [start] [stop- [stop- ] [startswap first and last reverse(sstart+ stop- recur on rest code fragment reversing the elements of sequence using linear recursion note that there are two implicit base case scenarioswhen start =stopthe implicit range is emptyand when start =stop- the implicit range has only one element in either of these casesthere is no need for actionas sequence with zero elements or one element is trivially equal to its reversal when otherwise invoking recursionwe are guaranteed to make progress towards base caseas the differencestop-startdecreases by two with each call (see figure if is evenwe will eventually reach the start =stop caseand if is oddwe will eventually reach the start =stop case the above argument implies that the recursive algorithm of code fragment is guaranteed to terminate after total of recursive calls since each call involves constant amount of workthe entire process runs in (ntime figure trace of the recursion for reversing sequence the shaded portion has yet to be reversed