designing recursive algorithms in generalan algorithm that uses recursion typically has the following formtest for base cases we begin by testing for set of base cases (there should be at least onethese base cases should be defined so that every possible chain of recursive calls will eventually reach base caseand the handling of each base case should not use recursion recur if not base casewe perform one or more recursive calls this recursive step may involve test that decides which of several possible recursive calls to make we should define each possible recursive call so that it makes progress towards base case parameterizing recursion to design recursive algorithm for given problemit is useful to think of the different ways we might define subproblems that have the same general structure as the original problem if one has difficulty finding the repetitive structure needed to design recursive algorithmit is sometimes useful to work out the problem on few concrete examples to see how the subproblems should be defined successful recursive design sometimes requires that we redefine the original problem to facilitate similar-looking subproblems oftenthis involved reparameterizing the signature of the function for examplewhen performing binary search in sequencea natural function signature for caller would appear as binary search(datatargethoweverin section we defined our function with calling signature binary search(datatargetlowhigh)using the additional parameters to demarcate sublists as the recursion proceeds this change in parameterization is critical for binary search if we had insisted on the cleaner signaturebinary search(datatarget)the only way to invoke search on half the list would have been to make new list instance with only those elements to send as the first parameter howevermaking copy of half the list would already take (ntimenegating the whole benefit of the binary search algorithm if we wished to provide cleaner public interface to an algorithm like binary searchwithout bothering user with the extra parametersa standard technique is to make one function for public use with the cleaner interfacesuch as binary search(datatarget)and then having its body invoke nonpublic utility function having the desired recursive parameters you will see that we similarly reparameterized the recursion in several other examples of this ( reverselinear sumbinary sumwe saw different approach to redefining recursion in our good fibonacci implementationby intentionally strengthening the expectation of what is returned (in that casereturning pair of numbers rather than single number