# Class 28: Recursion with Helper Procedures

Back to Recursion Basics, Continued. On to Other Forms of List Recursion.

This outline is also available in PDF.

Held: Wednesday, 14 October 2009

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:

Notes:

• Yes, we will have a quiz on Friday. It will be on recursion (including, possibly, helper recursion).
• No, you don't get an assignment 7 to do over fall break.
• Reading for Friday: List Recursion, Revisited.

Overview:

• Delayed evaluation in recursive procedures.
• A strategy: Carry along intermediate results.
• Using recursive helpers.
• A term: Tail recursion.
• Designing recursive procedures.

## 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.

## Tail Recursion

• Note that the two forms of recurison 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.

Back to Recursion Basics, Continued. On to Other Forms of List Recursion.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Dec 11 09:38:45 2009.
The source to the document was last modified on Fri Aug 21 17:03:06 2009.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2009F/Outlines/outline.28.html`.

You may wish to validate this document's HTML ; ;

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright © 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.) This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit `http://creativecommons.org/licenses/by-nc/2.5/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.