@extends('template')

@section('title')
    Tips: Thinking about recursive problems
@stop

@section('content')

# Tips: Thinking about recursive problems

+ **Understand the pattern**

     Draw out the first couple of cases involving the
     smallest number of recursive calls. You should understand how to create
     the pattern given <B>any</B> arguments for the pattern.
+ **What is the base case?**

    Endless loops are bad. When does the recursive method stop?
+ **Identify a single recursion layer**

    What distinguishes <CODE>recursion_method(level)</CODE> from
    <CODE>recursion_method(level-1)</CODE>?  What is added on with
    each additional level of recursion?

+  **Figure out how to move to the next recursion layer**

    Once we have executed a single recursion layer, we need to move into
    position to execute the next recursion layer.  What is this pattern?
    It should be the same no matter which two recursion layers we are
    moving between.

+  **What is the next recursion layer call?**

    Generally, the arguments will have to be modified for the next level
    (or else we'd create an endless loop)
+  **How do we meet our invariant, if any?**

    In order for recursive methods to work, they must meet strictly
    defined behaviors.  Often, this means that objects must be placed
    in their starting positions before exiting the method
   (for drawing recursive picture patterns).


# Programming recursion solutions

+ Follow all the steps in <B>Thinking about recursion problems</B> (above),
 first.
+ Write all code on paper first.  Try it out line by line using your brain
 and pencil and paper (or whiteboard) with the simplest test cases to make sure it works.
+ Finally, type the code into the computer and test it out.  Do this
  incrementally, as you would for any program.  Try to type and test one
  method at a time using stubs for other methods.  Be sure that each
  test version will terminate!
* **SAVE** files FREQUENTLY
 It is very easy to accidentally create an endless loop when solving
 recursion problems.  If we try to run our program and it has an endless
 loop, we will hang the computer and perhaps be forced to restart.
+ Use (lots of) <B>print</B> statements in all your methods to help with debugging.
   It's a good idea, for example, to print out the values of all the parameters
to make sure your function is recursing the way you intend it to.

@include('/labs/lab12/_toc')

@stop