If a problem can be reduced to smaller instances of the same problem, then a recursive solution is likely to be easy to find and implement.
A recursive algorithm for a function definition normally contains two kinds of cases: one or more cases that include at least one recursive call and one or more stopping cases in which the problem is solved without any recursive calls.
When writing a recursive function definition, always confirm that the function will not produce infinite recursion.
When you define a recursive function, use the three criteria given in the subsection “Recursive Design Techniques” to confirm that the function is correct.
When you design a recursive function to solve a task, it is often necessary to solve a more general problem than the given task. This may be required to allow for the proper recursive calls, since the smaller problems may not be exactly the same problem as the given task. For example, in the binary search problem, the task was to search an entire array, but the recursive solution is an algorithm to search any portion of the array (either all of it or a part of it).