Held: Monday, 9 March 2015

Back to Outline 27 - Characters and Strings. On to Outline 29 - 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
• Morning EBoard 28 (Source a.m. 28)
• Afternoon EBoard 28 (Source p.m. 28)

Overview

• Basics of helper recursion.
• A term: Tail recursion.
• Why write tail recursive procedures?

Administrivia

• New partners!
• Friday the 13th falls on Friday this week. Be careful!
• I received email from one of you that said (approximately): "I was barely scraping by in my plan to complete the exam and everything else that I have to do this week, and then ..."
  • My goal is not to push you to the edge; my goal is to support you in learning and to push what you are able to do.
  • If you are in the first situation, talk to me. I'd rather see representative work. I'd also rather limit your stress level.
• Office hours again next week. Mostly normal (MTWF 10:00 plus assorted others).
  • http://rebelsky.youcanbook.me

Upcoming Work

• Exam 2.
  • Electronic version due 10:30 p.m. Thursday the 12th.
  • Epilogue due 11:00 p.m. on Thursday the 12th.
  • Printed version due start of class on Friday the 13th.
• Reading for Tuesday:
  • Review Recursion with Helper Procedures

Extra Credit Opportunities

Academic

• CS Table Friday - Read cartoons!
• Town Hall on Town Halls, noon or 7:30 p.m. on March 11.
• Post-break: April 1 Scholars Convocation on Implicit Bias.

Peer Support (Morning Section)

• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.

Peer Support (Afternoon Section)

• Belly Dancing Club Wednesday, 7-8 p.m. in Bucksbaum Dance Studio
• Men's Tennis Saturday at 9:00 and 4:30 in the Bear Field House.

Miscellaneous (Extra Credit)

• Fill out the American College Health Association's National College Health Assessment survey. (Yes, your response can be "I filled out the survey.") Almost all of the class has filled out the survey. Let's reach 100%! TODAY IS THE LAST DAY!

Other Good Things (No Extra Credit)

Assorted Exam Notes and Questions

I know I can't ask you a direct question about the exam, but could you answer the following?

You can ask me a direct question about the exam. I may not answer it, or a I may answer it obliquely. But you are certainly permitted to ask.

Any hints?

I've added hints to a few problems in which people asked for hints, particularly the one on speeding up code. You will also find it useful to look more deeply at the Q and A section of the exam, because the questions people ask can provide hints.

Have two people spent at least four hours on the exam or completed the exam?

Yes. That's among the reasons that there are now only seven problems.

Q (from Sam): What do you expect to get from the expression (> x (and y z))? (I think this is intended to mean "if x is greater than both y and z".) I find it useful to think about concrete values: What is (> 3 (and 1 5))?

A (from "volunteer"):

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 all the recursive calls are 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.

Clarity in Tail Recursion

Some programmers find tail recursion much easier to understand. It's certainly easier to chart. And that may make it easier to design. We can also keep track of what's going on a bit better.

Let's do an example: Let's count the number of bright colors in a list.

What should we keep track of along the way?

• The elements of the list we haven't examined yet.
• The count of the bright colors we've already seen.

When are we done?

• When there's nothing left in the list.

What do we return?

• The count.

What do we do in other situations?

• ...

Note: For whatever reason, I see some students who find tail recursion very natural and standard recursion confusing, and some students who find standard recursion confusing and tail recursion natural. I'll push you to work on both.

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.