used by the algorithm (in addition to the array ais also roughly proportional to nsince we need constant amount of memory space for each of the boxes in the trace at the time we make the final recursive call (for reversing an array by recursion nextlet us consider the problem of reversing the elements of an arrayaso 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 an array can be achieved by swapping the first and last elements and then recursively reversing the remaining elements in the array we describe the details of this algorithm in code fragment using the convention that the first time we call this algorithm we do so as reversearray( , , code fragment reversing the elements of an array using linear recursion note thatin this algorithmwe actually have two base casesnamelywhen and when moreoverin either casewe simply terminate the algorithmsince sequence with zero elements or one element is trivially equal to its reversal furthermorenote that in the recursive step we are guaranteed to make progress towards one of these two base cases if is oddwe will eventually reach the caseand if is evenwe will eventually reach the case the above argument immediately implies that the recursive algorithm of code fragment is guaranteed to terminate defining problems in ways that facilitate recursion to design recursive algorithm for given problemit is useful to think of the different ways we can subdivide this problem to define problems that have the same general structure as the original problem this process sometimes means we need to redefine the original problem to facilitate similar-looking subproblems for examplewith the reversearray algorithmwe added the parameters and so that recursive call to reverse the inner part of the array would have the same structure (and same syntaxas the call to reverse all of thenrather than