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.

4. 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) ===> ()
   

5. 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) ===> ()
   

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

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

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