Held: Monday, 13 October 2014

Back to Outline 25 - Recursion Basics, Continued. On to Outline 27 - Recursion with Helper Procedures, Continued.

Summary

We consider a different form of recursion, one based on the construction of recursive helpers that take additional parameters. Along the way, we consider the idea of tail recursion. We also explore how careless design of recursive procedures can inadvertently lead to slow execution.

Related Pages

• Reading: Helper Recursion
• Lab: Helper Recursion
• EBoard 26 (Source 26) (HTML 26)

Overview

• Basics of helper recursion.
• A term: Tail recursion.

Administrivia

• New partners
• Office hours today and next week
  • Normal (MThF 1:45-3:15; walking 1:15-1:45)
  • Mornings I will be in various places. If you want to find me, email me.
• Quizzes to be returned tomorrow (assuming that the people who missed on Friday make up Quiz 6 before then)

Upcoming Work

• Writeup: Problems 4l and 5b (due Wednesday): http://bit.ly/151-2014F-w26
• Exam 2 due Tuesday.
  • Epilogue due Wednesday night
• Reading for Tuesday:
  • List Recursion, Revisited

Extra Credit Opportunities

• Yes, you can suggest others
• Yes, you can suggest cool things to do on campus

Academic

• BCC Faculty Chat, Tuesday, October 14, 7pm
• CS Table, Friday: Hear about the Grace Hopper Celebration of Women in Computing

Peer Support

• Football (Saturday at 1pm)
• Swimming October 18: Alumni Weekend
• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC
• Men's Tennis (???)
• Women's Tennis (???)

Basics of Helper Recursion

• Write a helper procedure to do the real recursion
  • Typically has an extra parameter to accumulate partial results
• A few benefits
  • Sometimes clearer
  • Sometimes more efficient
  • Sometimes easier to get correct

Tail Recursion

• Note that the two forms of recursion we've seen (direct recursion and helper recursion) have a somewhat different post-recursion step
  • In the first kinds of recursive procedures we wrote, there's still work to do after the recursive call finishes.
  • In the helper-recursion procedures, once we're done with the recursive call, the result is ready; it requires no further processing (at least not within the helper).
• It turns out that there are particularly efficient ways to implement recursive procedures that do not further process recursive results.
• Because of this efficiency, we have a special term for such procedures. We call them tail-recursive procedures.
• If any recursive call is a the last operation of a procedure (that is, the "tail" of the procedure), then we say that the procedure is tail recursive.
  • If some work may be required after one of the recursive calls, then we say that the procedure is not tail recursive.

Old Notes

These are from a previous time I taught the class. I leave them around for historical reasons.

Delayed Evalution in Recursive Procedures

• A number of you have noted that recursion, as written, builds up a bunch of stuff to evaluate.
• For example, if we're summing the list '(2 3 5 7 11 13), we end up with
  (+ 2 (+ 3 (+ 5 (+ 7 (+ 11 (+ 13 (sum ())))))))
  before we start doing the addition.
• Similarly, in selecting only the names of dark colors from a list, we might end up with
  (cons "black" (cons "darkblue" (cons "darkgrey" (select-dark ()))))
  
• Once we get to the base case of the recursion, we can then start to build up the actual result.
• Some people find the delayed evaluation natural, others find it awkward.
• For the latter group, we look for a strategy that helps us evaluate partial results along the way.

Helper Recursion

• The model that we call helper recursion (and that many of our colleagues call "tail recursion") adds an extra parameter to the recursive procedure
  • That extra parameter carries along partial/intermediate results
• For example, in summing the list (2 3 5 7 11 13), we might have

  partial-sum            unexplored-elements
  0                      (2 3 5 7 11 13)
  2                      (3 5 7 11 13)
  5                      (5 7 11 13)
  8                      (7 11 13)
  15                     (11 13)
  26                     (13)
  39                     ()

• When we run out of elements, we can use the intermediate result as our final result
• However, there's a small problem with this strategy: When a client makes the first call to the procedure, they won't necessarily understand the purpose of the extra parameter.
  • Hence, we make the modified procedure a helper to the top-level procedure.
  • The top-level procedure is responsible for filling in the extra parameter of the helper.