base of solving many problems is repetition.

we have alredy seen iteration; all loops are iterative constructs.

Recursion is another form of repetition, but rather than solve the same problem in
each iteration, it breaks a problem down into identical but smaller problems, and each
repetition solves one of the smaller problems, until we reach a trivial, or given
solution.

The trivial solution is called the base case of the recursion.  It is how we know
that we should stop the recursion process. The breaking down of the problem into 
an action (optional) and smaller problems is the called the recursive case.

note that at each step of recursion, WE DON'T CARE how each of the smaller problems is 
solved.  We just assume that they are, and use the solution of those smaller problems
to construct the solution to the problem as a whole.

Designing a recursive solution to a problem :

1. what part of the solution can you contribute directly?
2. what smaller but identical problem hasa solution that, when taken with your 
   solution, can solve the whole shebang?
3. when does the process end, i.e. what is the base case?

when designing recursive methods, remember three things

1. The method definition must contain logic that involves passing a parameter
   and leads to different cases; usually an if block or a switch statement.
2. One or more of the cases should provide a solution that does not require 
   recursion.
3. One of more must include a recursive call on a smaller problem component.

if we miss case 1, there is no way to track recursive progress.
if we miss case 2, there is no way to end recursion
if we miss case 3, there is no recursion, unless it is by proxy.

Infinite recursion - stack overflow.  Why is this?  Show stack frames.

If recursive call returns a value, base case must return the value.

Recursion is often elegant, simple, difficult to follow.  

Tracing recursive calls can be very complicated.  


Debugging tips

- does the method have at least one parameter?
- does the method have a statement that tests a parameter and leads to different cases
- do you consider all possible cases
- does at least one case contain a recursive call
- do the recursive calls correctly make the problem smaller
- if the recursion provides a correct result, will the method provide a correct result
- is at least one case a base case with no recursion
- are there enough base cases
- does each base case provide a correct value
- if a method returns a value, does each case return a value

Most problems can be solved either with a recursive or iterative solution.

recursion can seem simpler and more elegant
memory can be a problem for large values of n
this may go away on a larger system

See ExtendableList



recursive methods are often private, because they require access to structural elements
of the class not suitable for an ADT.


watch out for recursive inefficiency - avoid recursion in cases where the same
recursive call will be made more than one time.  Example, fibonacci sequence
f0 = 1; f1=1; fn = fn-1+fn-2

tail recursion - the last thing done is the recursive call.  This can always be 
replaced fairly simply with iteration.

mutual recursion - indirect recursion; a->b, b->c, c->a.