Recursion: tracing recursive methods, recursive searching and merge sort

Learning objectives

Identify the base case and the recursive call in a recursive method, and explain why a method whose base case is never reached recurses without end

Trace a recursive method by hand, listing each call with its own parameter values and local variables and each value returned as the calls unwind, and state the final result

Determine the result of a recursive method that traverses a String, an array or an ArrayList, or that works through the digits of an int

Explain that every recursive solution has an iterative equivalent and every loop a recursive one, and compare a recursive method with an equivalent loop

Trace a recursive binary search on a sorted array or ArrayList, stating which elements are examined and what value is returned

Trace a merge sort, showing how the array is divided down to single elements and how the sorted pieces are merged back together in order