CSC 153 Grinnell College Spring, 2005 Computer Science Fundamentals Laboratory Exercise

# Recursion: The Basics

## Goals

This lab introduces recursion −− a problem-solving technique in which procedures include one or more calls to the procedures themselves.

## Steps for this Lab

1. Consider the following procedure.

```(define longer-string
(lambda (str1 str2)
(if (< (string-length str1) (string-length str2))
str2
str1)))
```
1. Explain (in English) what this procedure does.

2. Test longer-string within the Scheme environment to illustrate how this procedure works in various circumstances.

2. Now consider the following recursive procedure longest-on-list that uses procedure longer-string.

```(define longest-on-list
(lambda (ls)
(if (null? (cdr ls))
(car ls)
(longer-string (car ls)
(longest-on-list (cdr ls))))))
```
1. Test longest-on-list in the following cases:

```(longest-on-list '("This" "is" "the" "forest" "primeval"))
(longest-on-list '("Wherefore" "art" "thou" "Romeo"))
(longest-on-list '("To" "be" "or" "not" "to" "be"))
(longest-on-list '("foo"))
(longest-on-list '("keep" "it" "short" "and" "sweet"))
(longest-on-list '("you" "can" "see" "the" "top"))
```
2. Write a paragraph that describes how this procedure longest-string works.

3. Apply longest-on-list to the empty list. Explain why you get the result returned.

3. Consider the following recursive procedure power:

```(define power
(lambda (n k)
(if (= k 1)
n
(* n (power n (- k 1))))))
```
1. Run `power` on several test cases that illustrate that this procedure performs as indicated by the pre- and post-conditions.

2. Write a paragraph to explain how power accomplishes its task.

With these examples as illustrations, the next three exercises ask you to write your own recursive procedures to solve a variety of problems.

1. Write a recursive procedure `countdown` that takes any non-negative integer `start` as its argument returns a list of all the positive integers less than or equal to `start`, in descending order:

```(countdown 5) ===> (5 4 3 2 1)
(countdown 1) ===> (1)
(countdown 0) ===> ()
```
2. Write a more general version of `list-of-zeroes`: a procedure `replicate` that takes two arguments, `size` and `item`, and returns a list of `size` elements, each of which is `item`:

```(replicate 6 'foo) ===> (foo foo foo foo foo foo)
(replicate 2 #f) ===> (#f #f)
(replicate 1 15) ===> (15)
(replicate 3 '(alpha beta)) ===> ((alpha beta) (alpha beta) (alpha beta))
(replicate 0 'help) ===> ()
```
3. Use the same problem-solving pattern illustrated in the reading for square-each-element to write a procedure `double-each-element` that takes a list of numbers and returns a list of their doubles:

```(double-each-element '(3 -62 41.4 17/4)) ===> (6 -124 82.8 17/2)
(double-each-element '(0)) ===> (0)
(double-each-element '()) ===> ()
```

The next exercises involve one main procedure (tally-by-parity) that uses a second procedure (tally-helper) as a helper procedure.

1. Consider the following procedures from the reading for this lab:

```(define tally-by-parity
(lambda (ls)
(tally-helper ls '(0 0))))
(define tally-helper
(lambda (ls ct-pair)
(cond ((null? ls) ct-pair)
((odd? (car ls))
(tally-helper (cdr ls)
(list (+ 1 (car ct-pair)) (cadr ct-pair))))
(else  (tally-helper (cdr ls)
(list (car ct-pair) (+ 1 (cadr ct-pair))))))))
```
1. Run tally-by-parity on the following examples to clarify what the procedure does.

```(tally-by-parity '(2 3 5 7 11 13))
(tally-by-parity '(0 1 2 3 4 5 6))
(tally-by-parity '(-8 124 0 124))
(tally-by-parity '())
```
2. Describe (in words) what each of these procedures do.

3. Explain in a few sentences how this solution works. Include a discussion of what procedure `tally-helper` does. Be sure to explain the purpose of both parameters ls and ct-pair within tally-helper.

2. Use the idea of tally-by-parity and tally-helper to write a procedure called `iota` that takes any non-negative integer `upper-bound` as argument and returns a list of the non-negative integers strictly less than `upper-bound`, in ascending order:

```(iota 6) ===> (0 1 2 3 4 5)
(iota 2) ===> (0 1)
(iota 1) ===> (0)
(iota 0) ===> ()
```

This document is available on the World Wide Web as

```http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-recursion.shtml
```

 created February 4, 1997 by John David Stone last revised January 26, 2005 by Henry M. Walker  For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.