2015-11-10 Lab

posted Nov 10, 2015, 4:57 AM by Samuel Konstantinovich   [ updated Nov 10, 2015, 5:25 AM ]
Goal: Tail Recursion
Do Now:

Consider how we calculate the sum of a list recursively:
(define sumList (lambda (L)
                  (if (null? L)
                      0
                      (+ (car L) (sumList (cdr L))))))
(sumList '(1 9 3 7 8 2 10 5))

Lets write the same function with a helper function:
(define sumListTail (lambda (L)
                      (sumHelp L 0)))
(define sumHelp (lambda (L ans)
      ;instead of adding onto the sumHelp outside of the function call
      ;keep adding onto the ans until you run out of elements.
)

The purpose of this is to keep all of the operations INSIDE the parenthesis of the recursive calls.
This means we can store partially calculated answers and not have to recalculate them.

Consider how we can re-write (fib n) using this method:
-The (fib n) function will start the helper function using the 1st two fib values.
-The helper function will have to keep track of your last two results, this will enable it to calculate the next value in one step.

DO NOT WRITE ANY CODE YET. After you show me your work for A + B on paper then you may turn on your monitor and start typing.
A) Decide how many parameters you need and discuss with your neighbors what they should be.
B) How will the recursion work now? Draw a diagram of how (fib 5) would work using your parameters.






Comments