# Class 15: Repetition with Recursion

Back to CGI Scripting, Continued. On to Recursion Lab.

Held: Wednesday, 12 February 2003

Summary: Today we begin to consider one of the most powerful tools in Scheme, recursion. Recursion allows you to repeat operations.

Related Pages:

Assignments

Notes:

Overview:

• Repetition.
• Recursion.
• Examples.
• Recursion in Scheme.

## Repetition

• You may recall that when we first considered algorithms we identified a number of key aspects of algortihms:
• variables: the ability to name things;
• conditions: the ability to choose between things;
• procedures: the ability to name (and parameterize) collections of steps;
• repetition: the ability to do something multiple times;
• input and output: the ability to get and report values.
• We've already seen how to do almost all of these things, except for repetition.
• Examples of repetition from baking:
• Stir the mix 50 times
• Bake until golden-brown.
• Examples of repetition from mathematics:
• Sum these values
• Find the smallest of these values
• Examples of repetition from everyday life:
• Naively find a name in the phone book
• Do I have a CD by Van Morrison?
• Examples of repetition from previous Scheme exercises:
• How long is this list?
• Is X a member of this list?

## Recursion

• In Scheme, the most common mechanism for repetition is recursion.
• To do something that involves repeated actions, you
• Do one action
• Repeat the rest
• Combine the results if necessary.
• For example, to stir your cake mix 50 times, you stir it one time and then stir it 49 more times.
• More generally, to stir a cake mix n times, you stir it one time and then n-1 more times.
• Similarly, to knead dough until its the right consistency, you knead it a little, check the consistency, and, if it's not the right consistency, knead it until its the right consistency.
• In the case of mathematics, to sum a list we might add the first value to the sum of the remaining values (or add the last value to the sum of the initial values).
• There are a few key aspects to recursive design:
• You need to know when you're done (and what to do when you're done). This aspect of recursive design is called the base case.
• You need to know what to do when you're not done. Here, you should do a little, try again, and then perhaps combine the results. This aspect of recursive design is called the recursive case.
• You need to be sure that you're getting closer to the base case (otherwise you'll never stop).

## Some Examples

• We'll look together at how we might solve a few recursive list-based examples as a way of thinking about the problem. I've included a variety of possibilities.
• sum, sum the elements in a list.
• member: Determine if a value is in a list.
• length: Find the length of a list
• We'll assume that the built-in `length` procedure does not exist.
• smallest: Find the smallest value in a list of numbers.
• average: Find the average value in a list of numbers.
• increment-elements: Add two to each number in a list of numbers.
• increment elements (revised): Add two to each number in a list of many different kinds of values.
• The code is not in the outline because I don't want to bias your answers.

## Recursion in Scheme

• Here's the form of a typical recursive procedure:
```(define proc
(lambda (val)
(if (base-case-test)
(base-case val)
(combine (partof val)
(proc (update val))))))
```
• When the value you're working with is a list and your base case is the null list, the form is somewhat simpler:
```(define proc
(lambda (lst)
(if (null? lst)
null-case
(combine (onestep (car val))
(proc (cdr val))))))
```

## History

Thursday, 16 January 2003 [Samuel A. Rebelsky]

• First version, created mostly automatically from previous course.

Wednesday, 12 February 2003 [Samuel A. Rebelsky]

Back to CGI Scripting, Continued. On to Recursion Lab.

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 Tue May 6 09:29:45 2003.
The source to the document was last modified on Wed Feb 12 09:34:36 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Outlines/outline.15.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu