Recursive techniques

• A recursive algorithm is one that is defined in terms of itself. This means that, when the steps of the algorithm are written down, one of the steps refers to the same algorithm by name. When implemented, the subroutine will include one or more calls to the original algorithm.
• Recursion is a method of solving a problem where the solution depends on solving increasingly smaller instances of the same problem.
• In a recursive program, there must always be at least one base case so that the recursion stops eventually.
• The general case is a statement that expresses the solution to a problem in terms of a reference to a smaller version of that same problem. 
• Every recursive algorithm must eventually stop calling itself; otherwise it will only stop when it has used up all of the available memory, which is known as stack overflow.
• When you write a recursive algorithm, you must use the following criteria:

  • Define a base case
  • Define the general case, referencing a version of the problem that decreases in size
  • When the algorithm is run, the base case will always be reached
• One of the main reasons that recursion is used is because many data structures are, by their nature, recursive. This means that it is more intuitive to process them recursively. A good example of this is the traversal algorithm for a binary tree.
• Recursive algorithms tend to have fewer steps than non-recursive solutions. This means that they are easier for humans to read. However, they are not necessarily very easy to trace or debug, as you need to be familiar with the call stack and how it is used. Having multiple concurrent versions of the same procedure can be confusing.
• Recursive algorithms use more memory. Because a stack frame has to be added to the stack with each recursive call, and values of any local variables (including values passed in for parameters) need to be stored until the stack frame is removed from the call stack, the memory allocation is greater than that of an iterative function. For the same reasons, recursion can be slow; time needs to be spent on stack operations to support recursion.