Week 8

• Return test
• Collect homework projects

Quiz

Recursion

• Start with example: n!
  • n! = n*(n-1)*(n-2)*…*1
  • or
  • n! = n*(n-1)!
  • n! = n*(n-1)*(n-2)!
  • n! = n*(n-1)*…*1!
  •     in 'nature' the number of ways to order n things
• Do the code for n!
  • Do as for loop
  • Do recursively
• Fibonaci numbers
  • fib(1) = 0
  • fib(2) = 1
  • fib(n) = fib(n-2) + fib(n-1) for n>2
  • Found in nature:
  •     originally number of rabbits over time
  •     number of petals on flowers
  •     number of rings on a pine cone

   

• Find the sum of integers from 1 to N

{

System.out.println("1+2+...+100=%d\n",Sum(1,100));

}

 ...

int Sum(int a,int b)

{

if(a==b)

    return a;

else

    return Sum(a,(a+b)/2)  + Sum(1+(a+b)/2,b);

}

• General form:
  • Has a general piece and can be reduced to smaller version of original problem
  • Has a stopping/base case
• Proof by induction
  • Prove for n=1 (or 0)
  • Prove if true for n, then also true for n+1
• Watch for infinite recursion
  • Must decrease values or scope between calls
  • Don’t start out of range

• Do example, traverse a list of  nodes in a list recursively
•     show by ordering statements can do in-order or reverse order

• Watch for recursion at end!!  More efficient to do as a loop

• Searching a maze problem.
  • Exhaustive search
  • recursive

• In class try Chapter 8 problem #1, #9
•     no loops

• Give out homework
  • Talk about searching linearly O(n) to find
  • Ask if there’s a better way
  • Show binary search
  • Talk about O(log n)