Recursion Lecture Notes

Recursion illustrated in one photograph.


Weiss's Four Rules for designing recursive algorithms.


1.  Always have at least one case that can be solved WITHOUT recursion ("base case"). p298


2.  Any recursive call must make progress towards a base case ("make progress")  p 298


3.  Assume the recursive call works. ("You gotta believe")  p302


4.  Never duplicate work by solving the same instance of a problem in separate recursive calls.
    ("Compound interest rule")  p 305

    Example, Fibonacci numbers.
    f(n) = f(n-1) + f(n-2)
    f(0) = 0
    f(1) = 1


Dr. Dalbey's Guidelines for when NOT to use recursion

1.   Compound Interest Rule
2.   When the formula is not recursive.
3.   When there's an obvious non-recursive solution (iteration).
4.   Usually, avoid tail recursion, because a while loop is simpler,
     uses less memory, and is faster.
     Example:  factorial.   f(n) = n * f(n-1)


When to use recursion

1.   When a solution has elements that call itself, when the definition is defined
     in terms of itself
     AND
     it doesn't use too much memory
     AND
     it isn't too slow.

2.   When it provides an "elegant" solution.
     The programmer doesn't have to explicitly manage partial solutions.



Comparison of Iterative and Recursive solution

Iterative
 Recursive
public static long sumOfDigits(long x)
{
      long sum = 0;
      while (x > 0)
      {
          sum += x%10;
          x = x/10;
      }
      return sum;
}		  public static long sumOfDigits(long x)
  {
       if (x < 10)
       {
            return x;
       }      
      return (x % 10) + sumOfDigits( x / 10 );
   }
     
(Notice: No "sum" variable)




Trace of a recursive algorithm
 
                17 <--+
                      ^ 17
SumOfDigits(7352) = 2 +                  <--+
                                            ^ 15
                       SumOfDigits(735) = 5 +                 <--+
                                                                 ^ 10
                                             SumOfDigits(73) = 3 +     <--+
                                                                          ^
                                                                   SumOfDigits(7) = 7